A213668 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of a pair of endvertices joined by n internally disjoint paths of length 2 (the n-ary generalized theta graph THETA_{2,2,...2}; n>=1, 1<=k<=n+2).

1, 3, 1, 0, 6, 4, 1, 0, 7, 10, 5, 1, 0, 9, 16, 15, 6, 1, 0, 11, 25, 30, 21, 7, 1, 0, 13, 36, 55, 50, 28, 8, 1, 0, 15, 49, 91, 105, 77, 36, 9, 1, 0, 17, 64, 140, 196, 182, 112, 45, 10, 1, 0, 19, 81, 204, 336, 378, 294, 156, 55, 11, 1

Offset: 1

Author

Emeric Deutsch, Jul 06 2012

Keywords

• nonn
• tabf

Comments

Row n>=2 contains n+1 entries.

Sum of entries in row n=3*2^n-1 = A052940(n) = A153893(n) = A055010(n+1) = A083329(n+1).

The graph G(n) is the join of the graph consisting of 2 isolated vertices and the graph consisting of n isolated vertices. Then the expression of the domination polynomial follows from Theorem 12 of the Akbari et al. reference.

Examples

			Row 1 is 1,3,1 because the graph G(1) is the path abc; there are 1 dominating subset of size 1 ({b}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
Row 2 is 0,6,4,1 because the graph G(2) is the cycle a-b-c-d-a and has dominating subsets ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, and abcd (see A212634).
Triangle starts:
1,3,1;
0,6,4,1;
0,7,10,5,1;
0,9,16,15,6,1;
		

References

• S. Akbari, S. Alikhani, and Y. H. Peng, Characterization of graphs using domination polynomials, European J. Comb., 31, 2010, 1714-1724.

Links

• S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
• T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926.

Crossrefs

Cf. A052940, A153893, A055010, A083329, A212634

Programs

Maple

p := proc (n) options operator, arrow: ((1+x)^n-1)*((1+x)^2-1)+x^n+x^2 end proc: for n to 12 do seq(coeff(p(n), x, k), k = 1 .. n+2) end do; # yields sequence in triangular form

Mathematica

T[n_, k_] := SeriesCoefficient[((1+x)^n-1) ((1+x)^2-1)+x^n+x^2, {x, 0, k}];
Table[T[n, k], {n, 1, 9}, {k, 1, n+2}] // Flatten (* Jean-François Alcover, Dec 06 2017 *)

Formula

The generating polynomial of row n is p(n)=((1+x)^n-1)*((1+x)^2-1)+x^n+x^2; by definition, p(n) is the domination polynomial of the graph G(n).

Bivariate g.f.: x*z/(1-x*z)-2*x*z/(1-z)+x*z*(1+x)*(2+x)/(1-z-x*z).

T(n,3)=n^2 for n!=3.