A213667 Number of dominating subsets with k vertices in all the graphs G(n) (n>=1) obtained by taking n copies of the path P_3 and identifying one of their endpoints (a star with n branches of length 2).
1, 6, 16, 40, 98, 238, 576, 1392, 3362, 8118, 19600, 47320, 114242, 275806, 665856, 1607520, 3880898, 9369318, 22619536, 54608392, 131836322, 318281038, 768398400, 1855077840, 4478554082, 10812186006, 26102926096, 63018038200, 152139002498, 367296043198
Offset: 1
Examples
a(2)=6 because (i) the graph G(1) is the path P_3=abc with 3 dominating subsets of size 2 (ab,ac,bc); (ii) the graph G(2) is the path P_5=abcde with 3 dominating subsets of size 2 (ad,bd,be); the graphs G(n) (n>=3) do not have dominating subsets of size 2.
Links
- Colin Barker, Table of n, a(n) for n = 1..1000
- S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251 [math.CO], 2009.
- É. Czabarka, L. Székely, and S. Wagner, The inverse problem for certain tree parameters, Discrete Appl. Math., 157, 2009, 3314-3319.
- T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, Recurrence relations and splitting formulas for the domination polynomial, arXiv:1206.5926 [math.CO], 2012.
- Index entries for linear recurrences with constant coefficients, signature (3,-1,-1).
Programs
-
Maple
a := proc (n) if n = 1 then 1 elif n = 2 then 6 elif n = 3 then 16 else 2*a(n-1)+a(n-2)+2 end if end proc: seq(a(n), n = 1 .. 32);
-
Mathematica
Table[2 Fibonacci[n, 2] + LucasL[n, 2]/2 - KroneckerDelta[n - 1] - 1, {n, 20}] (* Vladimir Reshetnikov, Sep 16 2016 *) -
PARI
Vec(x*(1+3*x-x^2-x^3)/((1-x)*(1-2*x-x^2)) + O(x^50)) \\ Colin Barker, Mar 16 2016
Formula
a(1)=1, a(2)=6, a(3)=16, a(n) = 2*a(n-1) + a(n-2) + 2 for n>=4.
G.f.: (1 + x)/(1 - 2*x - x^2) - 1/(1 - x) - x.
a(k) = sum(A213666(n,k), n>=1).
a(n) = A001333(n+1)-1 for n>=2.
a(n) = (-2+(1-sqrt(2))^(1+n)+(1+sqrt(2))^(1+n))/2 for n>1. - Colin Barker, Mar 16 2016