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.

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,2

Comments

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.

Links

Table of n, a(n) for n=1..55.

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".]

Example

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.  ...

Crossrefs

Row 2 appears to be (essentially) A107383 (or twice A061279).

The main diagonal is A320501.

Rows 3,4,5 are A320482, A320483, A320484.

Sequence in context: A092514 A106641 A191785 * A140957 A197250 A275578

Adjacent sequences: A320497 A320498 A320499 * A320501 A320502 A320503

Keyword

nonn,tabl

Author

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

Status

approved