The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296515 Number of edges in a maximal planar graph with n vertices. 3
0, 0, 1, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 102, 105, 108, 111, 114, 117, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 153, 156, 159, 162, 165, 168, 171, 174 (list; graph; refs; listen; history; text; internal format)
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
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.
K. Stephenson, Circle Packing: A Mathematical Tale, Notices Amer. Math. Soc. 50 (2003).
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.
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
Sequence in context: A337244 A366847 A031193 * A008585 A008486 A135943
KEYWORD
nonn,easy
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 13 09:43 EDT 2024. Contains 373383 sequences. (Running on oeis4.)