A289021 Number of maximal independent vertex sets and minimal vertex covers in the n-Apollonian network.

4, 5, 15, 845, 403227665, 64175114443109790962237345, 264288160993294964501375691029638701718807009656135518176301450923295365341665

Offset: 1

Author

Andrew Howroyd, Sep 01 2017

Keywords

• nonn

Comments

Term a(8) has 233 decimal digits.

The size of the largest maximal independent vertex set, the independence number, is given by 3^(n-1). For n > 1, the size of the smallest such set, the independent domination number, is given by 3^(n-2).

Also, for n > 1 the number of independent vertex sets and vertex covers in the (n-1)-Apollonian network.

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..9
• Eric Weisstein's World of Mathematics, Apollonian Network
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover
• Eric Weisstein's World of Mathematics, Vertex Cover

Crossrefs

Cf. A291773.

Programs

Mathematica

{1, 3} . # & /@ NestList[Function[{t, u}, {t^3 + u^3, t u^2}] @@ # &, {1, 1}, 6] (* Eric W. Weisstein, Sep 27 2017 *)

PARI

\\ here t0..t1 are for 0..1 outside vertices included in set
T(t0,t1,x) = {[t0^3+t1^3*x, t0*t1^2]}
p(n,x)={my(v=[x,1]); for(i=2,n,v=T(v[1],v[2],x)); v[1]+3*v[2]*x}
a(n)=p(n,1);