A350815 Array read by antidiagonals: T(m,n) is the number of minimum dominating sets in the m X n king graph.

1, 2, 2, 1, 4, 1, 4, 2, 2, 4, 3, 16, 1, 16, 3, 1, 12, 4, 4, 12, 1, 8, 4, 3, 256, 3, 4, 8, 4, 64, 1, 144, 144, 1, 64, 4, 1, 32, 8, 16, 79, 16, 8, 32, 1, 13, 8, 4, 4096, 9, 9, 4096, 4, 8, 13, 5, 208, 1, 1024, 1656, 1, 1656, 1024, 1, 208, 5, 1, 80, 13, 64, 408, 64, 64, 408, 64, 13, 80, 1

Offset: 1

Author

Andrew Howroyd, Jan 17 2022

Keywords

• nonn
• look
• tabl

Comments

The minimum size of a dominating set is the domination number which in the case of an m X n king graph is given by (ceiling(m/3) * ceiling(n/3)).

Examples

			Table begins:
============================================
m\n | 1  2  3    4    5   6      7     8
----+---------------------------------------
  1 | 1  2  1    4    3   1      8     4 ...
  2 | 2  4  2   16   12   4     64    32 ...
  3 | 1  2  1    4    3   1      8     4 ...
  4 | 4 16  4  256  144  16   4096  1024 ...
  5 | 3 12  3  144   79   9   1656   408 ...
  6 | 1  4  1   16    9   1     64    16 ...
  7 | 8 64  8 4096 1656  64 243856 29744 ...
  8 | 4 32  4 1024  408  16  29744  3600 ...
     ...
		

Links

• Stephan Mertens, Table of n, a(n) for n = 1..946 (first 276 terms from Andrew Howroyd)
• Stephan Mertens, Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph, arXiv:2408.08053 [math.CO], Aug 2024.
• Eric Weisstein's World of Mathematics, King Graph
• Eric Weisstein's World of Mathematics, Minimum Dominating Set

Crossrefs

Rows 1..3 are A347633, A350816, A347633.

Main diagonal is A347554.

Cf. A075561, A218663 (dominating sets), A286849 (minimal dominating sets), A303335, A350818, A350819.

Formula

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

T(3*m, 3*n) = 1; T(3*m+1, 3*n) = (m^2 + 5*m + 2)^n; T(3*m+2, 3*n) = (m+2)^n.

T(3*m-1, 3*n-1) = A350819(m, n).