A213655 Number of dominating subsets of the theta-graph TH(2,2,n) (n>=1). A tribonacci sequence with initial values 13, 23, and 41.

13, 23, 41, 77, 141, 259, 477, 877, 1613, 2967, 5457, 10037, 18461, 33955, 62453, 114869, 211277, 388599, 714745, 1314621, 2417965, 4447331, 8179917, 15045213, 27672461, 50897591, 93615265, 172185317, 316698173, 582498755

Offset: 1

Author

Emeric Deutsch, Jun 18 2012

Keywords

• nonn
• easy

Comments

A theta-graph is a graph consisting of two vertices of degree three, connected by three paths of one or more edges each. In the theta-graph TH(2,2,n) the three paths have 2, 2, and n edges, respectively.

a(n) = Sum_{k>=1} A213654(n,k).

Examples

			a(1)=13. TH(2,2,1) is the graph obtained from the cycle ABCD by joining vertices A and C. All 2^4 - 1 = 15 nonempty subsets of {A,B,C,D} are dominating with the exception of {B} and {D}.
		

References

• S. Alikhani and Y. H. Peng, Dominating sets and domination polynomials of certain graphs, II, Opuscula Math., 30, No. 1, 2010, 37-51.

Links

• S. Alikhani and Y. H. Peng, Introduction to domination polynomial of a graph, arXiv:0905.2251.
• Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Crossrefs

Cf. A213654.

Programs

Maple

a := proc (n) if n = 1 then 13 elif n = 2 then 23 elif n = 3 then 41 else a(n-1)+a(n-2)+a(n-3) end if end proc: seq(a(n), n = 1 .. 30);

Mathematica

LinearRecurrence[{1, 1, 1}, {13, 23, 41}, 30] (* Jean-François Alcover, Dec 02 2017 *)

Formula

a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 4; a(1)=13, a(2)=23, a(3)=41.

G.f.: -x*(13+10*x+5*x^2)/(-1+x+x^2+x^3). - R. J. Mathar, Jul 22 2022