A320500 - OEIS

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

(list; table; graph; refs; listen; history; text; internal format)

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