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