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,1

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).

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

Table of n, a(n) for n=1..30.

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).

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

Example

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}.

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 *)

Crossrefs

Cf. A213654.

Sequence in context: A339867 A135283 A225519 * A119488 A165350 A236418

Adjacent sequences: A213652 A213653 A213654 * A213656 A213657 A213658

Keyword

nonn,easy

Author

Emeric Deutsch, Jun 18 2012

Status

approved