A303335 -id:A303335

Search: a303335 -id:a303335

Displaying 1-5 of 5 results found.

page 1

A350815

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

+10
8

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

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

OFFSET

1,2

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

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

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

EXAMPLE

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

...

CROSSREFS

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

Main diagonal is A347554.

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

KEYWORD

nonn,look,tabl

AUTHOR

Andrew Howroyd, Jan 17 2022

STATUS

approved

A332390

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

+10
6

0, 1, 1, 2, 6, 2, 1, 10, 10, 1, 2, 15, 20, 15, 2, 4, 52, 52, 52, 52, 4, 3, 105, 179, 141, 179, 105, 3, 4, 175, 418, 801, 801, 418, 175, 4, 8, 481, 1167, 2950, 7770, 2950, 1167, 481, 8, 9, 1028, 3498, 9792, 34790, 34790, 9792, 3498, 1028, 9, 10, 2000, 9074, 47527, 184318, 204372, 184318, 47527, 9074, 2000, 10

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

OFFSET

1,4

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..120

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

FORMULA

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

EXAMPLE

Array begins:

================================================================

m\n | 1 2 3 4 5 6 7 8

----+-----------------------------------------------------------

1 | 0 1 2 1 2 4 3 4 ...

2 | 1 6 10 15 52 105 175 481 ...

3 | 2 10 20 52 179 418 1167 3498 ...

4 | 1 15 52 141 801 2950 9792 47527 ...

5 | 2 52 179 801 7770 34790 184318 1305358 ...

6 | 4 105 418 2950 34790 204372 1593094 14720683 ...

7 | 3 175 1167 9792 184318 1593094 16260853 231301551 ...

8 | 4 481 3498 47527 1305358 14720683 231301551 4570906041 ...

...

CROSSREFS

Rows 1..4 are A302655, A332392, A332393, A332394.

Main diagonal is A332391.

Cf. A286849, A303114, A303118, A303335, A303378.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Feb 10 2020

STATUS

approved

A303156

Number of minimum total dominating sets in the n X n king graph.

+10
4

0, 6, 8, 35, 1, 8684, 208, 604, 1192, 276696, 1362, 2, 2986, 32, 38772, 28520, 441984, 1024, 5047188

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

OFFSET

1,2

LINKS

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

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

CROSSREFS

Main diagonal of A303335.

Cf. A302401, A303116, A332391.

KEYWORD

nonn,more

AUTHOR

Eric W. Weisstein, Apr 19 2018

EXTENSIONS

a(6)-a(19) from Andrew Howroyd, Apr 21 2018

STATUS

approved

A303378

Array read by antidiagonals: T(m,n) = total domination number of the m X n king graph.

+10
4

1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, 2, 3, 4, 3, 2, 2, 3, 4, 4, 4, 3, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 5, 4, 4, 4, 5, 6, 5, 4, 6, 6, 6, 6, 4, 5, 6, 6, 6, 5, 6, 7, 8, 7, 6, 5, 6, 6, 6, 6, 6, 6, 8, 8, 8, 8, 6, 6, 6, 6, 7, 6, 6, 8, 9, 8, 9, 8, 9, 8, 6, 6, 7

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

OFFSET

1,2

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, Total Dominating Set

EXAMPLE

Table begins:

=======================================================

m\n| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

---+---------------------------------------------------

1 | 1 2 2 2 3 4 4 4 5 6 6 6 7 8 8 8 ...

2 | 2 2 2 2 3 4 4 4 5 6 6 6 7 8 8 8 ...

3 | 2 2 2 2 3 4 4 4 5 6 6 6 7 8 8 8 ...

4 | 2 2 2 4 4 4 6 6 6 8 8 8 10 10 10 12 ...

5 | 3 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

6 | 4 4 4 4 6 8 8 8 10 12 12 12 14 16 16 16 ...

7 | 4 4 4 6 7 8 9 10 11 12 14 14 16 17 18 19 ...

8 | 4 4 4 6 8 8 10 12 12 14 16 16 18 20 20 22 ...

9 | 5 5 5 6 9 10 11 12 15 16 17 18 21 22 23 24 ...

...

CROSSREFS

Main diagonal is A302401.

Cf. A300358, A303114, A303335.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Apr 22 2018

STATUS

approved

A350817

Number of minimum total dominating sets in the 2 X n king graph.

+10
1

1, 6, 9, 4, 8, 89, 56, 16, 64, 780, 304, 64, 384, 5472, 1536, 256, 2048, 33920, 7424, 1024, 10240, 194304, 34816, 4096, 49152, 1053696, 159744, 16384, 229376, 5488640, 720896, 65536, 1048576, 27721728, 3211264, 262144, 4718592, 136642560, 14155776, 1048576

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

OFFSET

1,2

LINKS

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

Eric Weisstein's World of Mathematics, King Graph

Eric Weisstein's World of Mathematics, Total Dominating Set

Index entries for linear recurrences with constant coefficients, signature (0,0,0,12,0,0,0,-48,0,0,0,64).

FORMULA

a(n) = 12*a(n-4) - 48*a(n-8) + 64*a(n-12) for n > 13.

G.f.: x*(1 + 6*x + 9*x^2 + 4*x^3 - 4*x^4 + 17*x^5 - 52*x^6 - 32*x^7 + 16*x^8 + 64*x^10 + 64*x^11 - 64*x^12)/((1 - 2*x^2)^3*(1 + 2*x^2)^3).

a(4*k) = 4^k; a(4*k+1) = 2*k*4^k for k > 0; a(4*k+2) = (k + 1)*(41*k + 48)*4^k/8; a(4*k+3) = (5*k + 9)*4^k.

MATHEMATICA

LinearRecurrence[{0, 0, 0, 12, 0, 0, 0, -48, 0, 0, 0, 64}, {1, 6, 9, 4, 8, 89, 56, 16, 64, 780, 304, 64, 384}, 40] (* Michael De Vlieger, Jan 19 2022 *)

PROG

(PARI) Vec((1 + 6*x + 9*x^2 + 4*x^3 - 4*x^4 + 17*x^5 - 52*x^6 - 32*x^7 + 16*x^8 + 64*x^10 + 64*x^11 - 64*x^12)/((1 - 2*x^2)^3*(1 + 2*x^2)^3) + O(x^40))

(PARI) a(n)={my(k=n\4); 4^k*if(n%2, if(n%4==1, (k==0) + 2*k, 5*k + 9), if(n%4==0, 1, (k + 1)*(41*k + 48)/8))}

CROSSREFS

Row 2 of A303335.

Cf. A350816.

KEYWORD

nonn,easy

AUTHOR

Andrew Howroyd, Jan 17 2022

STATUS

approved

page 1

Search completed in 0.009 seconds