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
Examples
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. ...
Links
- 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".]
Comments