login
Number of dominating subsets 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}).
1

%I #29 Feb 19 2024 04:37:20

%S 7,13,25,49,95,185,361,705,1379,2701,5297,10401,20447,40241,79281,

%T 156353,308643,609813,1205881,2386481,4726463,9367401,18577497,

%U 36865665,73199171,145419549,289038817,574766401,1143442495,2275683169,4530762977,9023630465,17977560259

%N Number of dominating subsets 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}).

%H S. Alikhani and Emeric Deutsch, <a href="http://arxiv.org/abs/1305.3734">More on domination polynomial and domination root</a> (Previous title: "Graphs with domination roots in the right half-plane"), arXiv preprint arXiv:1305.3734 [math.CO], 2013-2014.

%H S. Alikhani and Y. H. Peng, <a href="http://arxiv.org/abs/0905.2251">Introduction to domination polynomial of a graph</a>, arXiv:0905.2251 [math.CO], 2009.

%H T. Kotek, J. Preen, F. Simon, P. Tittmann, and M. Trinks, <a href="http://arxiv.org/abs/1206.5926">Recurrence relations and splitting formulas for the domination polynomial</a>, arXiv:1206.5926 [math.CO], 2012.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,-1,-2)

%F a(n) = Sum(k=1..n+2) A213662(n,k).

%F a(n) = a(n-1) + a(n-2) + a(n-3) + 2^(n-2) for n>=4. [corrected by _Harvey P. Dale_, Aug 11 2012]

%F From _R. J. Mathar_, Jul 03 2012: (Start)

%F a(n) = 2^(n+1) + A000213(n+2).

%F G.f.: -x*(-7+8*x+7*x^2+6*x^3) / ( (2*x-1)*(x^3+x^2+x-1) ). (End)

%e a(1)=7 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}).

%p a[1] := 7: a[2] := 13: a[3] := 25: for n from 4 to 35 do a[n] := a[n-1]+a[n-2]+a[n-3]+2^(n-2) end do: seq(a[n], n = 1 .. 35);

%t RecurrenceTable[{a[1]==7,a[2]==13,a[3]==25,a[n]==a[n-1]+a[n-2]+ a[n-3]+ 2^(n-2)},a,{n,40}] (* _Harvey P. Dale_, Aug 11 2012 *)

%Y Cf. A213662.

%K nonn

%O 1,1

%A _Emeric Deutsch_, Jun 29 2012