A304561 Number of minimum total dominating sets in the n-triangular (Johnson) graph.

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

Andrew Howroyd, Table of n, a(n) for n = 2..200

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

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