OFFSET

0,4

COMMENTS

{a(n)} is a monotonic increasing sequence because a maximal planar graph of order n can be generated on n + 1 nodes. Therefore a(n) <= a(n + 1).

Maximal planar graphs of order n > 5 are not unique.

|E(G_2n)| = (2n - 1) + 2*Sum_{k=0..(floor(log_2(n - 1)))} floor((n - 1)/2^k) where |E(G_2n)| is the size of a minimal planar graph G of order 2n.

Number of edges of a maximal 3-degenerate graph of order n (this class includes 3-trees). The intersection of this class and maximal planar graphs is the Apollonian networks (planar 3-trees); neither class contains the other. - Allan Bickle, Nov 14 2021

a(n) is the number of blocks to dig (in a staircase fashion) to get out of a hole of depth n in Minecraft. - Max R Anderson, Oct 19 2023

LINKS

Stefano Spezia, Table of n, a(n) for n = 0..10000

Allan Bickle, Structural results on maximal k-degenerate graphs, Discuss. Math. Graph Theory 32 4 (2012), 659-676.

Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.

Dawei He, Yan Wang, and Xingxing Yu, The Kelmans-Seymour conjecture I, arXiv:1511.05020 [math.CO], 2015.

D. R. Lick and A. T. White, k-degenerate graphs, Canad. J. Math. 22 (1970), 1082-1096.

Mathematics Stack Exchange, You dig a hole in Minecraft straight down n blocks, how many blocks must you dig to get out?

K. Stephenson, Circle Packing: A Mathematical Tale, Notices Amer. Math. Soc. 50 (2003).

Squid Tamar-Mattis, Planar Graphs and Wagner's and Kuratowski's Theorems, REU (2016).

Eric Weisstein's World of Mathematics, Kuratowski Reduction Theorem, Polyhedral Graph

David R. Wood, A Simple Proof of the Fary-Wagner Theorem, arXiv:cs/0505047 [math.CO], 2005.

Index entries for linear recurrences with constant coefficients, signature (2,-1).

FORMULA

a(n) = floor(6/2^n) + 3n - 6 (see comments section of A008486).

G.f.: x^2 + 3*x^3/(x - 1)^2. - R. J. Mathar, Apr 14 2018

E.g.f.: 6 + x*(x + 6)/2 + 3*exp(x)*(x - 2). - Stefano Spezia, Feb 13 2023

a(n) = 3*(n - 2) for n >= 3. - Max R Anderson, Oct 19 2023

MATHEMATICA

CoefficientList[Series[(x^2 (1 + x + x^2))/(x - 1)^2, {x, 0, 60}], x] (* or *) LinearRecurrence[{2, -1}, {0, 0, 1, 3}, 60] (* Robert G. Wilson v, Mar 04 2018 *)

CROSSREFS

KEYWORD

nonn,easy

AUTHOR

Joseph Wheat, Jonathan Sondow, Feb 28 2018

STATUS

approved