|
| |
|
|
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).
|
|
3
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
Table of n, a(n) for n=4..75.
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
|
|
|
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: binom(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
|
|
|
CROSSREFS
|
Cf. A212634.
Sequence in context: A219234 A155675 A217285 * A087108 A021687 A063422
Adjacent sequences: A212632 A212633 A212634 * A212636 A212637 A212638
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
Emeric Deutsch, Jun 17 2012
|
|
|
STATUS
|
approved
|
| |
|
|
