A212635 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with cardinality k of the wheel W_n (n >= 4, 1 <= k <= n).
4, 6, 4, 1, 1, 10, 10, 5, 1, 1, 10, 20, 15, 6, 1, 1, 9, 29, 35, 21, 7, 1, 1, 7, 35, 63, 56, 28, 8, 1, 1, 8, 36, 94, 118, 84, 36, 9, 1, 1, 9, 39, 120, 207, 201, 120, 45, 10, 1, 1, 10, 45, 145, 312, 402, 320, 165, 55, 11, 1, 1, 11, 55, 176, 429, 693, 715, 484, 220, 66, 12, 1
Offset: 4
Examples
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;
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
Crossrefs
Cf. A212634.
Programs
-
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 *)
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).
Comments