|
|
A213669
|
|
Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the double star graph G(n) obtained by joining with an edge the centers of two star trees each having n+1 vertices (n>=1, k>=2).
|
|
0
|
|
|
4, 4, 1, 1, 6, 11, 6, 1, 1, 6, 17, 26, 22, 8, 1, 1, 8, 28, 58, 78, 68, 37, 10, 1, 1, 10, 45, 120, 212, 262, 230, 140, 56, 12, 1, 1, 12, 66, 220, 495, 794, 936, 822, 535, 250, 79, 14, 1, 1, 14, 91, 364, 1001, 2002, 3005, 3446, 3045, 2072, 1071, 406, 106, 16, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
Number of entries in row n is 2n+1.
Sum of entries in row n is (2^n +1)^2 = A028400(n).
The Matula-Goebel number of the rooted tree obtained from G(n), by selecting the center of one of the trees as the root, is 2^n*(2^n-th prime); (knowing this, see A212630 for another approach to find this sequence).
Closely related to the connected domination polynomial of the n-book graph (divided by x^2), which is 1 less in the 3rd-to-last term of each row. - Eric W. Weisstein, May 12 2017
|
|
LINKS
|
|
|
FORMULA
|
The generating polynomial of row n is (x^n + x(1+x)^n)^2; this is the domination polynomial of the graph G(n).
The domination polynomial of the double star graph obtained by joining with an edge the center of a star tree having m+1 vertices and the center of a star tree having n+1 vertices is (x^m+x(1+x)^m)*(x^n + x(1+x)^n) (m,n >=1).
|
|
EXAMPLE
|
Row 1 is 4,4,1 because the graph G(1) is the path abcd; there are 4 dominating subsets of size 2 (ac,ad,bc,bd), 4 dominating subsets of size 3 (abc,abd,acd,bcd) and 1 dominating subset of size 4 (abcd).
Triangle starts:
4, 4, 1;
1, 6, 11, 6, 1;
1, 6, 17, 26, 22, 8, 1;
1, 8, 28, 58, 78, 68, 37, 10, 1;
|
|
MAPLE
|
P := proc (n) options operator, arrow: (x^n+x*(1+x)^n)^2 end proc: for n to 9 do seq(coeff(P(n), x, k), k = 2 .. 2*n+2) end do; # yields sequence in triangular form
|
|
MATHEMATICA
|
T[n_, k_] := SeriesCoefficient[(x^n + x (1 + x)^n)^2, {x, 0, k}];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|