A213662 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) obtained by joining each vertex of the path graph P_{n+1} on n+1 vertices with an additional vertex (the join of K_1 and P_{n+1}).

3, 3, 1, 2, 6, 4, 1, 1, 8, 10, 5, 1, 1, 8, 18, 15, 6, 1, 1, 7, 25, 33, 21, 7, 1, 1, 7, 29, 57, 54, 28, 8, 1, 1, 8, 32, 82, 110, 82, 36, 9, 1, 1, 9, 37, 106, 187, 191, 118, 45, 10, 1, 1, 10, 45, 133, 280, 372, 308, 163, 55, 11, 1, 1, 11, 55, 170, 391, 633, 673, 470, 218, 66, 12, 1

Offset

1,1

Comments

Row n contains n + 2 entries.

Sum of entries in row n = A213663(n).

Links

Table of n, a(n) for n=1..75.

S. Alikhani and E. Deutsch, Graphs with domination roots in the right half-plane, arXiv preprint arXiv:1305.3734, 2013

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.

Formula

The generating polynomial g(n) =g(n,x) of row n (= domination polynomial of the graph G(n)) satisfies the recursion relation g(n) = x*g(n-1) + x*g(n-2) + x*g(n-3) + x*(1+x)^(n-2) (n>=4); g(1)=3*x+3*x^2+x^3; g(2)=2*x+6*x^2+4*x^3+x^4; g(3)=x+8*x^2+10*x^3+5*x^4+x^5.

Example

Row 1 is 3,3,1 because the graph G(1) is the triangle abc; there are 3 dominating subsets of size 1 ({a}, {b}, {c}), 3 dominating subsets of size 2 ({a,b}, {a,c}, {b,c}), and 1 dominating subset of size 3 ({a,b,c}).
T(n,1)=1 for n>=3 because the common vertex of the n triangles is the only dominating subset of size k=1.
Triangle starts:
3,3,1;
2,6,4,1;
1,8,10,5,1;
1,8,18,15,6,1;
1,7,25,33,21,7,1;

Maple

g[1] := 3*x+3*x^2+x^3: g[2] := 2*x+6*x^2+4*x^3+x^4: g[3] := x+8*x^2+10*x^3+5*x^4+x^5: for n from 4 to 22 do g[n] := sort(expand(x*g[n-1]+x*g[n-2]+x*g[n-3]+x*(1+x)^(n-2))) end do: for n to 10 do seq(coeff(g[n], x, k), k = 1 .. n+2) end do; # yields sequence in triangular form

Crossrefs

Cf. A213663

Sequence in context: A309507 A306690 A160326 * A213657 A215596 A268676

Adjacent sequences: A213659 A213660 A213661 * A213663 A213664 A213665

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 29 2012

Status

approved