A289021 - OEIS

%I #18 Jan 10 2020 05:30:49

%S 4,5,15,845,403227665,64175114443109790962237345,

%T 264288160993294964501375691029638701718807009656135518176301450923295365341665

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

%C Term a(8) has 233 decimal digits.

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

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

%H Andrew Howroyd, <a href="/A289021/b289021.txt">Table of n, a(n) for n = 1..9</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ApollonianNetwork.html">Apollonian Network</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

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

%o (PARI) \\ here t0..t1 are for 0..1 outside vertices included in set

%o T(t0,t1,x) = {[t0^3+t1^3*x, t0*t1^2]}

%o p(n,x)={my(v=[x,1]); for(i=2,n,v=T(v[1],v[2],x)); v[1]+3*v[2]*x}

%o a(n)=p(n,1);

%Y Cf. A291773.

%K nonn

%O 1,1

%A _Andrew Howroyd_, Sep 01 2017