OFFSET
4,1
COMMENTS
The entries in row n are the coefficients of the domination polynomial of the wheel W_n (see the Alikhani and Peng arxiv reference).
LINKS
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
J. L. Arocha, B. Llano, The number of dominating k-sets of paths, cycles and wheels, arXiv preprint arXiv:1601.01268 [math.CO], 2016.
Eric Weisstein's World of Mathematics, Domination Polynomial
Eric Weisstein's World of Mathematics, Wheel Graph
FORMULA
Denoting by pw(n,x) the domination polynomial of the wheel W_n, we have the recurrence relation pw(n,x) = x(pw(n-1,x) + pw(n-2,x) + pw(n-3,x)) + x(1+x)^{n-4}; pw(4,x) = 4x + 6x^2 + 4x^3 + x^4, pw(5,x) = x + 10x^2 + 10x^3 + 5x^4 + x^5, pw(6,x) = x + 10x^2 + 20x^3 + 15x^4 + 6x^5 + x^6.
If pc(n,x) is the domination polynomial of the cycle C_n (see A212634), then the domination polynomial of the wheel W_n is x*(1 + x)^(n-1) + pc(n,x) (see Corollary 2 in the Alikhani & Peng reference).
EXAMPLE
Row 4 is [4,6,4,1] because all nonempty subsets of the wheel W_4 are dominating: binomial(4,j) of size j (j=1,2,3,4).
T(7,2)=9 because in the wheel W_7 with vertices A (center), B, C, D, E, F, G the dominating subsets of size 2 are {B,E}, {C,F}, {D,G}, {A, B}, {A,C}, {A,D}, {A,E}, {A,F}, and {A, G}.
Irregular triangle starts:
4, 6, 4, 1;
1, 10, 10, 5, 1;
1, 10, 20, 15, 6, 1;
1, 9, 29, 35, 21, 7, 1;
MAPLE
pc := proc (n) if n = 1 then x elif n = 2 then x^2+2*x elif n = 3 then x^3+3*x^2+3*x else sort(expand(x*(pc(n-1)+pc(n-2)+pc(n-3)))) end if end proc: p := proc (n) options operator, arrow: sort(expand(x*(1+x)^(n-1)+pc(n-1))) end proc: for n from 4 to 15 do seq(coeff(p(n), x, k), k = 1 .. n) end do; # yields sequence in triangular form
MATHEMATICA
pc[n_] := pc[n] = Which[n == 1, x, n == 2, x^2 + 2*x, n == 3, x^3 + 3*x^2 + 3*x, True, Sort[Expand[x*(pc[n - 1] + pc[n - 2] + pc[n - 3])]]];
p[n_] := Sort[Expand[x*(1 + x)^(n - 1) + pc[n - 1]]];
Table[Coefficient[p[n], x, k], {n, 4, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 24 2017, after Emeric Deutsch *)
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jun 17 2012
STATUS
approved