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

Comments

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

Links

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

Formula

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

Example

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

Crossrefs

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

Sequence in context: A066761 A108920 A079405 * A201353 A072048 A161841

Adjacent sequences: A332344 A332345 A332346 * A332348 A332349 A332350

Keyword

nonn,tabl

Author

Andrew Howroyd, Feb 10 2020

Status

approved