A107383 -id:A107383 - cp's OEIS frontend

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

1, 2, 2, 2, 4, 2, 3, 6, 6, 3, 4, 12, 8, 12, 4, 5, 20, 22, 22, 20, 5, 7, 36, 40, 79, 40, 36, 7, 9, 64, 82, 194, 194, 82, 64, 9, 12, 112, 176, 537, 544, 537, 176, 112, 12, 16, 200, 340, 1519, 1882, 1882, 1519, 340, 200, 16, 21, 352, 722, 4011, 6490, 8197, 6490, 4011, 722, 352, 21

Offset: 1

Andrew Howroyd, Feb 10 2020

Also the number of minimal vertex covers in the m X n king graph.

			Array begins:
=====================================================
m\n | 1   2   3    4     5      6       7       8
----+------------------------------------------------
  1 | 1   2   2    3     4      5       7       9 ...
  2 | 2   4   6   12    20     36      64     112 ...
  3 | 2   6   8   22    40     82     176     340 ...
  4 | 3  12  22   79   194    537    1519    4011 ...
  5 | 4  20  40  194   544   1882    6490   20534 ...
  6 | 5  36  82  537  1882   8197   36301  144409 ...
  7 | 7  64 176 1519  6490  36301  201611 1009321 ...
  8 | 9 112 340 4011 20534 144409 1009321 6214593 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..496
Eric Weisstein's World of Mathematics, King Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Rows 1..4 are A000931(n+6), A107383(n+2), A332348, A332349.
Main diagonal is A288956.
Cf. A197054 (grid graph), A218663 (dominating sets), A245013 (independent sets), A286849 (minimal dominating sets).

T(n,m) = T(m,n).

A320500 Symmetric array read by antidiagonals: T(m,n) = number of "minimal connected vertex covers" of an m X n grid, for m>=1, n>=1.

Original entry on oeis.org

1, 2, 2, 1, 4, 1, 1, 6, 6, 1, 1, 12, 11, 12, 1, 1, 20, 30, 30, 20, 1, 1, 36, 75, 110, 75, 36, 1, 1, 64, 173, 382, 382, 173, 64, 1, 1, 112, 434, 1270, 1804, 1270, 434, 112, 1, 1, 200, 1054, 4298, 7888, 7888, 4298, 1054, 200, 1

Offset: 1

N. J. A. Sloane, Oct 22 2018, based on email from Don Knuth, Oct 20 2018

Take the m X n grid graph with m*n vertices, each connected to four neighbors [except only two at the corners, otherwise three on the edges]. We ask for a vertex cover that is connected. It should also be minimal: if we leave out any element and it is no longer a connected vertex cover.

			The array begins:
1,   2,    1,     1,      1,        1,         1,          1,           1, ...
2,   4,    6,    12,     20,       36,        64,        112,         200, ...
1,   6,   11,    30,     75,      173,       434,       1054,        2558, ...
1,  12,   30,   110,    382,     1270,      4298,      14560,       49204, ...
1,  20,   75,   382,   1804,     7888,     36627,     166217,      755680, ...
1,  36,  173,  1270,   7888,    46416,    287685,    1751154,    10656814, ...
1,  64,  434,  4298,  36627,   287685,   2393422,   19366411,   157557218, ...
1, 112, 1054, 14560, 166217,  1751154,  19366411,  208975042,  2255742067, ...
1, 200, 2558, 49204, 755680, 10656814, 157557218, 2255742067, 32411910059, ...
...
The T(3,3) = 11 minimal connected vertex covers of a 3 X 3 grid are:
X.X  .X.  X..  X.X  X..  X..  ..X  ...  ...  .X.  ...
...  ...  ..X  ...  ..X  .X.  .X.  .X.  .X.  ...  X.X
X.X  X.X  X..  .X.  X..  ...  ...  X..  ..X  .X.  ...

M. R. Garey and D. S. Johnson, The rectilinear Steiner tree problem is NP-complete, SIAM J. Applied Math., 32 (1977), 826-834. [They call these "connected node covers".]

Row 2 appears to be (essentially) A107383 (or twice A061279).
The main diagonal is A320501.
Rows 3,4,5 are A320482, A320483, A320484.

cp's OEIS Frontend

A332347 Array read by antidiagonals: T(m,n) is the number of maximal independent sets in the m X n king graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula