A286913 -id:A286913 - cp's OEIS frontend

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

0, 1, 1, 1, 7, 1, 2, 43, 43, 2, 3, 277, 969, 277, 3, 5, 1777, 23663, 23663, 1777, 5, 8, 11407, 571099, 2180738, 571099, 11407, 8, 13, 73219, 13807469, 198906617, 198906617, 13807469, 73219, 13, 21, 469981, 333735575, 18169793971, 68534828391, 18169793971, 333735575, 469981, 21

Offset: 1

Andrew Howroyd, May 15 2017

			Table starts:
======================================================================
m\n| 1     2        3           4              5                 6
---|------------------------------------------------------------------
1  | 0     1        1           2              3                 5 ...
2  | 1     7       43         277           1777             11407 ...
3  | 1    43      969       23663         571099          13807469 ...
4  | 2   277    23663     2180738      198906617       18169793971 ...
5  | 3  1777   571099   198906617    68534828391    23650967140325 ...
6  | 5 11407 13807469 18169793971 23650967140325 30833670159649637 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..276
Eric Weisstein's World of Mathematics, Edge Cover
Eric Weisstein's World of Mathematics, Grid Graph

Rows 1-3 are A000045(n-1), A286911, A288031.
Main diagonal is A286913.
Cf. A210662, A099390, A089934, A218354.

T(1,1) corrected by Andrew Howroyd, Jun 04 2017

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Original entry on oeis.org

1, 5, 431, 555195, 10286937043, 2692324030864335, 9852929684161379901975, 501079193080617800221189943995, 352690403996687922642590703716802346343, 3426297680513758764075706102615040790667832304415, 458508006189588425325361635000918336126387961057365005349963

Offset: 1

Andrew Howroyd, Jan 28 2023

nonn

For n > 1, a(n) is the number of connected edge covers in the n X n grid graph.

			The a(2) = 5 connected spanning subgraphs are the following subgraphs and their rotations and reflections.
   o---o   o---o
   |       |   |
   o---o   o---o

Andrew Howroyd, Table of n, a(n) for n = 1..15
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A359993.

Cf. A007341, A053765, A080691, A286913, A359989.

a(n) = A053765(n) - A359989(n).

A288027 Number of minimal edge covers in the grid graph P_n X P_n.

Original entry on oeis.org

0, 2, 38, 1834, 419710, 356269056, 1163645044100, 15000387107144576, 749707067231291403016

Offset: 1

Andrew Howroyd, Jun 04 2017

A minimal edge cover is an edge cover such that the removal of any edge in the cover destroys the covering property. Equivalently, these are the edge covers whose connected components are stars.

			In the 3 X 3 grid, the minimal edge covers up to rotation and reflection are:
.__.__.    .__.__.    .__.__.    .__.__.    .__.__.    .__.  .
.__.__.    .  .  .    .__.  .    .  .__.    .  |  .    .  |  |
.__.__.    |  |  |    .__.  |    |__.  |    |  .__|    |  .__.
The first two of these need to be counted 2 and 4 times and the rest which have no symmetry 8 times so a(3) = 38.

Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Minimal Edge Cover

Main diagonal of A288025.

Cf. A286913.

a(1) corrected by Andrew Howroyd, Jan 29 2023

A359989 Number of edge cuts in the n X n grid graph.

Original entry on oeis.org

0, 11, 3665, 16222021, 1089224690733, 1150229180575982641, 19332960184149905415396841, 5191795779341747010730275139276101, 22300392508126626453613075681944644703634073, 1532492114568208344599582951444206568577948454351297761

Offset: 1

Andrew Howroyd, Jan 28 2023

nonn

			The a(2) = 11 edge cuts are the following subgraphs and their rotations and reflections. The illustrations show the edge sets that must be removed to disconnect the graph.
    o---o    o---o   o---o   o---o
    |                |       |   |
    o   o    o---o   o---o   o---o
The first two of these show minimal edge cuts.

Eric Weisstein's World of Mathematics, Edge Cut
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A359990.

Cf. A053765, A286913, A359992.

a(n) = A053765(n) - A359992(n).

A288031 Number of edge covers in the grid graph P_3 X P_n.

Original entry on oeis.org

1, 43, 969, 23663, 571099, 13807469, 333735575, 8066926825, 194989463233, 4713185791699, 113924706164937, 2753729539353359, 66561737202707371, 1608896152717277333, 38889412128248718215, 940014912175876488361, 22721558047666401897553, 549213840574693856578267

Offset: 1

Andrew Howroyd, Jun 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200

Row 3 of A286912.

Cf. A286911, A286913.

Empirical: a(n) = 20*a(n-1)+100*a(n-2)+24*a(n-3) -95*a(n-4)+10*a(n-5)+8*a(n-6) for n>6.

Empirical g.f.: x*(1 + 23*x + 9*x^2 - 41*x^3 + 2*x^4 + 8*x^5) / (1 - 20*x - 100*x^2 - 24*x^3 + 95*x^4 - 10*x^5 - 8*x^6). - Colin Barker, Jun 11 2017

cp's OEIS Frontend

A286912 Array read by antidiagonals: T(m,n) = number of edge covers in the grid graph P_m X P_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A359992 Number of connected spanning subgraphs in the n X n grid graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A288027 Number of minimal edge covers in the grid graph P_n X P_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A359989 Number of edge cuts in the n X n grid graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A288031 Number of edge covers in the grid graph P_3 X P_n.

Views

Author

Keywords

Links

Crossrefs

Formula