A213657 Irregular triangle read by rows: T(n,k) is the number of dominating subsets with k vertices of the graph G(n) consisting of an edge ab, n vertices c_1, c_2, ..., c_n, and 2n edges ac_i, bc_i (i=1..n). (n triangles with a common edge).
3, 3, 1, 2, 6, 4, 1, 2, 7, 10, 5, 1, 2, 9, 16, 15, 6, 1, 2, 11, 25, 30, 21, 7, 1, 2, 13, 36, 55, 50, 28, 8, 1, 2, 15, 49, 91, 105, 77, 36, 9, 1, 2, 17, 64, 140, 196, 182, 112, 45, 10, 1, 2, 19, 81, 204, 336, 378, 294, 156, 55, 11, 1
Offset: 1
Examples
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)=2 for n >= 2 because {a} and {b} are the only dominating subsets of size k=1.
Triangle starts:
3, 3, 1;
2, 6, 4, 1;
2, 7, 10, 5, 1;
2, 9, 16, 15, 6, 1;
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.
Crossrefs
Cf. A181565
Programs
-
Maple
T := proc (n, k) if k = n then (1/2)*(n+1)*(n+2) else 2*binomial(n, k-1)+binomial(n, k-2) end if end proc: for n to 12 do seq(T(n, k), k = 1 .. n+2) end do; # yields sequence in triangular form
-
Mathematica
T[n_, k_] := If[k==n, (n+1)*(n+2)/2, 2*Binomial[n, k-1]+Binomial[n, k-2]]; Table[T[n, k], {n, 1, 10}, {k, 1, n+2}] // Flatten (* Jean-François Alcover, Dec 09 2017 *)
Formula
Generating polynomial of row n is x^n + x*(2+x)*(1+x)^n; this is the domination polynomial of the graph G(n).
T(n,n) = (n+1)*(n+3)/2; T(n,k) = 2*binomial(n, k-1) + binomial(n, k-2) if k != n.
Comments