A291773 Domination number of the n-Apollonian network.

1, 1, 3, 4, 7, 16, 43, 124, 367, 1096, 3283, 9844, 29527, 88576, 265723, 797164, 2391487, 7174456, 21523363, 64570084, 193710247, 581130736, 1743392203, 5230176604, 15690529807, 47071589416, 141214768243, 423644304724, 1270932914167, 3812798742496

Offset: 1

Author

Eric W. Weisstein, Aug 31 2017

Keywords

• nonn
• easy

Comments

Also, the connected domination number of the n-Apollonian network. - Andrew Howroyd, Jan 16 2018

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• Eric Weisstein's World of Mathematics, Apollonian Network
• Eric Weisstein's World of Mathematics, Connected Domination Number
• Eric Weisstein's World of Mathematics, Domination Number
• Index entries for linear recurrences with constant coefficients, signature (4,-3).

Crossrefs

Cf. A298105.

Programs

Mathematica

(* Start from Eric W. Weisstein, Jan 17 2018 *)
Join[{1, 1}, Table[(3^(n - 3) + 5)/2, {n, 3, 20}]]
Join[{1, 1}, Table[(3^n + 135)/54, {n, 3, 20}]]
Join[{1, 1}, (3^Range[3, 20] + 135)/54]
Join[{1, 1}, LinearRecurrence[{4, -3}, {3, 4}, 20]]
CoefficientList[Series[(1 - 3 x + 2 x^2 - 5 x^3)/(1 - 4 x + 3 x^2), {x, 0, 20}], x]
(* End *)

PARI

\\ here d0..d3 are for 0..3 outside vertices included in dominating set.
D(d0,d1,d2,d3) = {[min(3*d0,1+3*d1), min(d0+2*d1,1+d1+2*d2), min(2*d1+d2,1+2*d2+d3), min(3*d2,1+3*d3)]}
a(n)={my(v=[1,0,0,0]); for(i=2,n,v=D(v[1],v[2],v[3],v[4])); min(min(v[1],1+v[2]),min(2+v[3],3+v[4]))} \\ Andrew Howroyd, Sep 01 2017

PARI

Vec(x*(1 - 3*x + 2*x^2 - 5*x^3) / ((1 - x)*(1 - 3*x)) + O(x^40)) \\ Colin Barker, Oct 03 2017

Formula

a(n) = (3^(n-3) + 5) / 2 for n > 2. - Andrew Howroyd, Sep 01 2017

From Colin Barker, Oct 03 2017: (Start)

G.f.: x*(1 - 3*x + 2*x^2 - 5*x^3) / ((1 - x)*(1 - 3*x)).

a(n) = 4*a(n-1) - 3*a(n-2) for n>4.

(End)

a(n) = A289521(n-3) for n > 3. - Andrew Howroyd, Jan 16 2018

Extensions

a(7)-a(30) from Andrew Howroyd, Sep 01 2017