

A304561


Number of minimum total dominating sets in the ntriangular (Johnson) graph.


1



0, 3, 12, 80, 840, 630, 13440, 277200, 75600, 3326400, 116839800, 16216200, 1210809600, 65043178200, 5448643200, 617512896000, 47147109609600, 2639867630400, 422378820864000, 43505018548992000, 1742312636064000, 374016445875072000, 49991305310266320000, 1502744648605200000
(list;
graph;
refs;
listen;
history;
text;
internal format)



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

Table of n, a(n) for n=2..25.
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, (1811*t21*t^2+32*t^3)/18, if(n%3==1, 1, 4*t/3))/(t!*(2^t))} \\ Andrew Howroyd, May 20 2018


CROSSREFS

Cf. A303048, A303227.
Sequence in context: A084565 A323634 A275488 * A303227 A182166 A303047
Adjacent sequences: A304558 A304559 A304560 * A304562 A304563 A304564


KEYWORD

nonn


AUTHOR

Eric W. Weisstein, May 14 2018


EXTENSIONS

a(9)a(25) from Andrew Howroyd, May 20 2018


STATUS

approved



