login
A304561
Number of minimum total dominating sets in the n-triangular (Johnson) graph.
4
0, 3, 12, 80, 840, 630, 13440, 277200, 75600, 3326400, 116839800, 16216200, 1210809600, 65043178200, 5448643200, 617512896000, 47147109609600, 2639867630400, 422378820864000, 43505018548992000, 1742312636064000, 374016445875072000, 49991305310266320000, 1502744648605200000
OFFSET
2,2
COMMENTS
In general, a dominating set on a triangular graph corresponds with an edge cover on a complete graph with optionally one vertex uncovered. In the case of n mod 3 == 1, a minimum total dominating set will correspond with one uncovered vertex and the remaining covered by trees of size 3. In the case of n mod 3 == 2, one of trees needs to be increased to size 4. In the case of n divisible by 3, one tree may be size 5 or two size 4 or all may be size 3 but without an uncovered vertex. - Andrew Howroyd, May 20 2018
LINKS
Eric Weisstein's World of Mathematics, Johnson Graph
Eric Weisstein's World of Mathematics, Total Dominating Set
Eric Weisstein's World of Mathematics, Triangular Graph
FORMULA
a(3*k+1) = (3*k+1)!/(2^k*k!), a(3*k+2) = 4*k*(3*k+2)!/(3*2^k*k!), a(3*k) = (18 - 11*k - 21*k^2 + 32*k^3)*(3*k)!/(18*2^k*k!). - Andrew Howroyd, May 20 2018
MATHEMATICA
Table[Piecewise[{{(2^-(n/3 + 1) (486 - 99 n - 63 n^2 + 32 n^3) n!)/(243 (n/3)!), Mod[n, 3] == 0}, {(2^((1 - n)/3) n!)/Gamma[(n + 2)/3], Mod[n, 3] == 1}, {(2^((8 - n)/3) n!)/(3 Gamma[(n - 2)/3]), Mod[n, 3] == 2}}], {n, 2, 30}]
PROG
(PARI) a(n)={my(t=n\3); n!*if(n%3==0, (18-11*t-21*t^2+32*t^3)/18, if(n%3==1, 1, 4*t/3))/(t!*(2^t))} \\ Andrew Howroyd, May 20 2018
CROSSREFS
Sequence in context: A323634 A373395 A275488 * A303227 A182166 A303047
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, May 14 2018
EXTENSIONS
a(9)-a(25) from Andrew Howroyd, May 20 2018
STATUS
approved