A290325 Number of minimal dominating sets (and maximal irredundant sets) in the complete tripartite graph K_{n,n,n}.

3, 15, 30, 51, 78, 111, 150, 195, 246, 303, 366, 435, 510, 591, 678, 771, 870, 975, 1086, 1203, 1326, 1455, 1590, 1731, 1878, 2031, 2190, 2355, 2526, 2703, 2886, 3075, 3270, 3471, 3678, 3891, 4110, 4335, 4566, 4803, 5046, 5295, 5550, 5811, 6078

Offset: 1

Author

Eric W. Weisstein, Jul 27 2017

Keywords

• nonn
• easy

Comments

When n>1 the minimal dominating sets consist of either a single vertex from any two of the partitions or all vertices from just one of the partitions. When n=1 only the later are minimal. - Andrew Howroyd, Jul 27 2017

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Complete Tripartite Graph
• Eric Weisstein's World of Mathematics, Maximal Irredundant Set
• Eric Weisstein's World of Mathematics, Minimal Dominating Set
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Programs

Mathematica

Rest[With[{nn = 50}, CoefficientList[Series[3 ((x^2 + x + 1)*Exp[x] - (2*x + 1)) + 3*x, {x, 0, nn}], x]*Range[0, nn]!]] (* or *) Table[3*(n^2 +1), {n,1,50}] (* G. C. Greubel, Aug 17 2017 *)

PARI

Vec(3*x*(1 + 2*x - 2*x^2 + x^3) / (1 - x)^3 + O(x^60)) \\ Colin Barker, Jul 27 2017

Formula

a(n) = 3*n^2 + 3 for n > 1. - Andrew Howroyd, Jul 27 2017

From Colin Barker, Jul 27 2017: (Start)

G.f.: 3*x*(1 + 2*x - 2*x^2 + x^3) / (1 - x)^3.

a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n > 4. (End)

E.g.f.: 3((x^2 + x + 1)*exp(x) - (2*x + 1)) + 3*x. - G. C. Greubel, Aug 17 2017

Extensions

a(6)-a(45) from Andrew Howroyd, Jul 27 2017

Maximal irredundant sets added to name by Eric W. Weisstein, Aug 17 2017