login
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).
1
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
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
Sequence in context: A054674 A186503 A213654 * A059574 A332395 A004600
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, Jun 30 2012
STATUS
approved