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).

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

Author

Emeric Deutsch, Jul 10 2012

Keywords

• nonn
• tabf

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

Examples

			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;
		

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

Crossrefs

Cf. A028400, A212630.

Programs

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 *)

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).