login
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
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
S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
S. Akbari, S. Alikhani, and Y. H. Peng, Characterization of graphs using domination polynomials, European J. Comb., 31, 2010, 1714-1724.
T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926 [math.CO], 2012.
Eric Weisstein's World of Mathematics, Book Graph
Eric Weisstein's World of Mathematics, Connected Dominating Set
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}];
Table[T[n, k], {n, 1, 9}, {k, 2, 2 n + 2}] // Flatten (* Jean-François Alcover, Dec 06 2017 *)
CROSSREFS
Sequence in context: A202024 A319703 A166361 * A046539 A198929 A172347
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jul 10 2012
STATUS
approved