

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 MatulaGoebel 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^nth prime); (knowing this, see A212630 for another approach to find this sequence).
Closely related to the connected domination polynomial of the nbook graph (divided by x^2), which is 1 less in the 3rdtolast term of each row.  Eric W. Weisstein, May 12 2017


LINKS

Table of n, a(n) for n=1..63.
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, 17141724.
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 (* JeanFrançois Alcover, Dec 06 2017 *)


CROSSREFS

Cf. A028400, A212630.
Sequence in context: A202024 A319703 A166361 * A046539 A198929 A172347
Adjacent sequences: A213666 A213667 A213668 * A213670 A213671 A213672


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Jul 10 2012


STATUS

approved



