A213664 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 a vertex with two consecutive vertices of the cycle graph C_n (n >=3).

2, 6, 4, 1, 0, 7, 10, 5, 1, 0, 5, 16, 15, 6, 1, 0, 2, 18, 30, 21, 7, 1, 0, 0, 14, 44, 50, 28, 8, 1, 0, 0, 7, 48, 89, 77, 36, 9, 1, 0, 0, 2, 39, 122, 160, 112, 45, 10, 1, 0, 0, 0, 23, 131, 261, 265, 156, 55, 11, 1, 0, 0, 0, 9, 110, 342, 498, 413, 210, 66, 12, 1

Offset

1,1

Comments

Row n contain n + 1 entries.

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

Links

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

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] (n>=6); g[3]=2x+6x^2+4*x^3+x^4; g[4]=7x^2+10x^3+5x^4+x^5; g[5]=5x^2+16x^3+15x^4+6x^5+x^6.

Example

Row 3 is 2,6,4,1 because G(3) is the square abcd with the additional edge bd; all nonempty subsets of {a,b,c,d} are dominating, with the exception of {a} and {c}.
Triangle starts:
2,6,4,1;
0,7,10,5,1;
0,5,16,15,6,1;
0,2,18,30,21,7,1;

Maple

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

Crossrefs

Cf. A213665

Sequence in context: A054674 A186503 A213654 * A059574 A332395 A004600

Adjacent sequences: A213661 A213662 A213663 * A213665 A213666 A213667

Keyword

nonn,tabf

Author

Emeric Deutsch, Jun 30 2012

Status

approved