login
Number of minimum total dominating sets in the n-ladder graph.
3

%I #19 Feb 27 2019 12:32:30

%S 1,4,1,16,9,1,64,16,1,169,25,1,361,36,1,676,49,1,1156,64,1,1849,81,1,

%T 2809,100,1,4096,121,1,5776,144,1,7921,169,1,10609,196,1,13924,225,1,

%U 17956,256,1,22801,289,1,28561,324,1,35344,361,1,43264,400,1,52441

%N Number of minimum total dominating sets in the n-ladder graph.

%C Each vertex can dominate up to three others. A ladder with a length that is an exact multiple of three can be dominated in only one way with 2n/3 vertices. - _Andrew Howroyd_, Apr 21 2018

%H Andrew Howroyd, <a href="/A303054/b303054.txt">Table of n, a(n) for n = 1..200</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TotalDominatingSet.html">Total Dominating Set</a>

%H <a href="/index/Rec#order_15">Index entries for linear recurrences with constant coefficients</a>, signature (0,0,5,0,0,-10,0,0,10,0,0,-5,0,0,1).

%F a(n) = 1 for n mod 3 = 0

%F = ((n^2 + 13*n + 4)/18)^2 for n mod 3 = 1

%F = ((n + 4)/3)^2 for n mod 3 = 2.

%F G.f.: x*(-1 - 4*x - x^2 - 11*x^3 + 11*x^4 + 4*x^5 + 6*x^6 - 11*x^7 - 6*x^8 + x^9 + 5*x^10 + 4*x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5.

%F a(n) = 5*a(n-3) - 10*a(n-6) + 10*a(n-9) - 5*a(n-12) + a(n-15) for n>15. - _Colin Barker_, Apr 23 2018

%e From _Andrew Howroyd_, Apr 21 2018: (Start)

%e a(9) = 1 because there is only one arrangement of 6 vertices that is totally dominating and no set with fewer vertices can be totally dominating:

%e .__o__.__.__o__.__.__o__.

%e | | |

%e .__o__.__.__o__.__.__o__.

%e (End)

%t Table[Piecewise[{{1, Mod[n, 3] == 0}, {((n^2 + 13 n + 4)/18)^2, Mod[n, 3] == 1}, {((n + 4)/3)^2, Mod[n, 3] == 2}}], {n, 58}] (* _Eric W. Weisstein_, Apr 23 2018 and _Michael De Vlieger_, Apr 21 2018 *)

%t Table[(916 + 392 n + 213 n^2 + 26 n^3 + n^4 - (-56 + 392 n + 213 n^2 + 26 n^3 + n^4) Cos[2 n Pi/3] + Sqrt[3] (-20 + 7 n + n^2) (28 + 19 n + n^2) Sin[2 n Pi/3])/972, {n, 20}] (* _Eric W. Weisstein_, Apr 23 2018 *)

%t LinearRecurrence[{0, 0, 5, 0, 0, -10, 0, 0, 10, 0, 0, -5, 0, 0, 1}, {1, 4, 1, 16, 9, 1, 64, 16, 1, 169, 25, 1, 361, 36, 1}, 20] (* _Eric W. Weisstein_, Apr 23 2018 *)

%t CoefficientList[Series[(-1 - 4 x - x^2 - 11 x^3 + 11 x^4 + 4 x^5 + 6 x^6 - 11 x^7 - 6 x^8 + x^9 + 5 x^10 + 4 x^11 - x^12 - x^13 - x^14)/(-1 + x^3)^5, {x, 0, 20}], x] (* _Eric W. Weisstein_, Apr 23 2018 *)

%o (PARI) a(n)={if(n%3==0, 1, if(n%3==1, (n^2 + 13*n + 4)/18, (n + 4)/3))^2} \\ _Andrew Howroyd_, Apr 21 2018

%o (PARI) Vec(x*(1 + 4*x + x^2 + 11*x^3 - 11*x^4 - 4*x^5 - 6*x^6 + 11*x^7 + 6*x^8 - x^9 - 5*x^10 - 4*x^11 + x^12 + x^13 + x^14) / ((1 - x)^5*(1 + x + x^2)^5) + O(x^60)) \\ _Colin Barker_, Apr 23 2018

%Y Row 2 of A303293.

%K nonn,easy

%O 1,2

%A _Eric W. Weisstein_, Apr 17 2018

%E Terms a(14) and beyond from _Andrew Howroyd_, Apr 21 2018