A003094 -id:A003094 - cp's OEIS frontend

A343873 Triangle read by rows: T(n,k) is the number of unlabeled connected planar graphs with n edges and k nodes (n >= 0, 1 <= k <= n + 1).

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 2, 3, 0, 0, 0, 1, 5, 6, 0, 0, 0, 1, 5, 13, 11, 0, 0, 0, 0, 4, 19, 33, 23, 0, 0, 0, 0, 2, 22, 67, 89, 47, 0, 0, 0, 0, 1, 19, 107, 236, 240, 106, 0, 0, 0, 0, 0, 13, 130, 486, 797, 657, 235, 0, 0, 0, 0, 0, 5, 130, 804, 2075, 2678, 1806, 551

Offset: 0

Andrew Howroyd, May 06 2021

First differs from A054923 in row n=9.

Terms may be computed using the tools geng and planarg in nauty.

			Triangle begins (n edges >= 0, k vertices >= 1):
  1;
  0, 1;
  0, 0, 1;
  0, 0, 1, 2;
  0, 0, 0, 2, 3;
  0, 0, 0, 1, 5,  6;
  0, 0, 0, 1, 5, 13,  11;
  0, 0, 0, 0, 4, 19,  33,  23;
  0, 0, 0, 0, 2, 22,  67,  89,  47;
  0, 0, 0, 0, 1, 19, 107, 236, 240, 106;
  0, 0, 0, 0, 0, 13, 130, 486, 797, 657, 235;
  ...

Georg Grasegger, Table of n, a(n) for n = 0..285 (rows 0..22) (terms 0..209 (rows 0..19) from Andrew Howroyd)
Brendan McKay and Adolfo Piperno, nauty and Traces

Row sums are A046091.
Column sums are A003094.
Main diagonal is A000055.
Subsequent diagonals are A001429, A001435, A001436 (same as for not necessarily planar graphs).
Cf. A049334 (transpose), A054923, A343870.

geng -c $k $n:$n | planarg -q | countg -q # Georg Grasegger, Jul 06 2023

A049340 Triangle read by rows: T(n,k) is the number of planar graphs with n >= 1 nodes and 0 <= k <= binomial(n,2) edges, all degrees even.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 4, 4, 6, 5, 5, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 3, 4, 7, 9, 15, 17, 22, 14, 16, 5, 4, 0, 1, 0, 0, 0

Offset: 1

Brendan McKay

			Triangle begins:
  1;
  1, 0;
  1, 0, 0, 1;
  1, 0, 0, 1, 1, 0, 0;
  1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0;
  1, 0, 0, 1, 1, 1, 3, 2, 2, 1, 1, 0, 1, 0, 0, 0;
  ...

Sean A. Irvine, Table of n, a(n) for n = 1..231, rows 1..11 flattened
Sean A. Irvine, Java program (github)

Rows sums give A049339.

Cf. A000944, A021103, A003094, A049334.

Entry revised by Sean A. Irvine, Jul 29 2021

A145270 Number of simple connected nonplanar graphs on n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 13, 207, 5143, 189195, 10663766, 989251266, 163746458178, 50329965610911

Offset: 0

Eric W. Weisstein, Oct 05 2008

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Nonplanar Graph
Eric Weisstein's World of Mathematics, Simple Graph

Cf. A145269.

a(n) = A001349(n) - A003094(n).

Edited by Max Alekseyev, Sep 18 2009
a(12) added by Max Alekseyev, Aug 17 2015
a(13) from Max Alekseyev, Feb 20 2025

A243321 Number of simple connected graphs with n nodes that are bipartite and planar.

Original entry on oeis.org

1, 1, 1, 3, 5, 16, 41, 158, 582, 2749, 13852, 80341, 503582, 3419670, 24533162, 184227017

Offset: 1

Travis Hoppe and Anna Petrone, Jun 03 2014

Travis Hoppe and Anna Petrone, Encyclopedia of Finite Graphs
T. Hoppe and A. Petrone, Integer sequence discovery from small graphs, arXiv preprint arXiv:1408.3644 [math.CO], 2014.
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.

Cf. A003216 (bipartite graphs), A003094 (planar graphs).

A164099 = Cases[Import["https://oeis.org/A164099/b164099.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[{0} ~Join~ A164099 + 1] (* Jean-François Alcover, Dec 03 2019, updated Mar 17 2020 *)

Inverse Euler transform of (A164099 + 1). - Falk Hüffner, May 10 2019

a(11)-a(16) added using tinygraph by Falk Hüffner, May 10 2019

A298446 Triangle T(n,k) read by rows: number of n-node connected graphs with rectilinear crossing number k (k=0..A014540(n)).

Original entry on oeis.org

1, 1, 2, 6, 20, 1, 99, 11, 1, 1, 646, 149, 38, 15, 1, 2, 1, 0, 0, 1, 5974, 3008, 1251, 542, 171, 80, 47, 12, 15, 7, 4, 1, 3, 0, 0, 1, 0, 0, 0, 1, 71885

Offset: 1

Eric W. Weisstein, Jan 19 2018

Computed up to n=8 using data provided by Geoffrey Exoo. (There appear to be some problems with n=9 data.)

T(9,1) >= 71335. - Eric W. Weisstein, Mar 28 2019

			Triangle begins:
1
1
2
6
20,1
99,11,1,1
646,149,38,15,1,2,1,0,0,1
5974,3008,1251,542,171,80,47,12,15,7,4,1,3,0,0,1,0,0,0,1

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Rectilinear Crossing Number

Cf. A014540 (rectilinear crossing number for K_n).

Cf. A298445 (counts for simple graph).

T(n,0) = A003094(n).
kmax(n) = A014540(n).
T(n,kmax(n)) = 1 for n > 4.
sum(k=0..kmax(n), T(n,k)) = A001349(n).

Corrected by Eric W. Weisstein, Mar 28 2019

A301425 Number of plane 5-regular simple connected graphs with 2n vertices.

Original entry on oeis.org

1, 0, 1, 1, 6, 14, 98, 529, 4035, 31009, 252386, 2073769, 17277113

Offset: 6

M. F. Hasler, Mar 20 2018

We count here plane graphs, i.e., graphs embedded in the plane, up to embedding-preserving isomorphism, while such sequences as A003094 count planar graphs (counted up to abstract isomorphism). In this we follow the nomenclature of Brendan McKay, cf. link.

			There is only a(6) = 1 planar 5-regular simple connected graph with 2n = 12 vertices, which is the icosahedral graph, cf. MathWorld link. If we label the vertices 1, ..., 9, A, B, C, they are connected as follows: 1 -> {2 3 4 5 6}, 2 -> {1 6 7 8 3}, 3 -> {1 2 8 9 4}, 4 -> {1 3 9 A 5}, 5 -> {1 4 A B 6}, 6 -> {1 5 B 7 2 }, 7 -> {2 6 B C 8}, 8 -> {2 7 C 9 3}, 9 -> {3 8 C A 4}, A -> {4 9 C B 5}, B -> {5 A C 7 6}, C -> {7 B A 9 8}.
For other numbers of vertices, the number of plane 5-regular simple connected graphs is as follows:
14 vertices: 0  graphs,
16 vertices: 1  graph,
18 vertices: 1  graph,
20 vertices: 6  graphs,
22 vertices: 14  graphs,
24 vertices: 98  graphs,
26 vertices: 529  graphs,
28 vertices: 4035  graphs,
30 vertices: 31009  graphs,
32 vertices: 252386  graphs,
34 vertices: 2073769 graphs,
36 vertices: 17277113 graphs. (From the McKay web page.)

B. D. McKay, Plane graphs (see also the section on Planar Graphs on this page).
Eric Weisstein's World of Mathematics, Icosahedral Graph.
Index to sequences related to planar graphs

Cf. A308489, A292109, A292972, A323281, A322917, A322929, A006821, A003094.

A307072 Number of simple connected graphs on n nodes with crossing number 1.

Original entry on oeis.org

0, 0, 0, 0, 1, 11, 149, 3008, 71335, 1814021

Offset: 1

Eric W. Weisstein, Mar 22 2019

			5-node: K_5.
6-node: includes K_{1,2,3}, (5-1)-lollipop, 2 X 3 queen, utility graph K_{3,3}.

Cf. A307071 (not necessarily connected graphs).

Cf. A003094 (connected graphs with crossing number 0).

a(9) from Eric W. Weisstein, Apr 17 2019

a(10) from Eric W. Weisstein, Apr 28 2019

A342213 Largest number of maximal planar node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 1, 5, 15, 35, 70, 126, 211

Offset: 1

Pontus von Brömssen, Mar 05 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

a(11) >= 381, because the complete 5-partite graph K_{1,1,3,3,3} has 381 maximal planar subgraphs.

			For 4 <= n <= 9, a(n) = binomial(n,4) = A000332(n) and the complete graph is optimal, but a(10) = 211 > 210 = binomial(10,4) with the optimal graph being the complete 6-partite graph K_{1,1,1,1,3,3}. The optimal graph is unique when 5 <= n <= 10.

Cf. A000332, A003094, A005470.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Lim_{n->oo} a(n)^(1/n) >= 381^(1/11) = 1.71644... .

A361368 Number of weakly connected simple planar digraphs with n unlabeled nodes.

Original entry on oeis.org

2, 13, 199, 8782, 897604

Offset: 2

Manfred Scheucher, Mar 09 2023

M. Kirchweger, M. Scheucher, and S. Szeider, SAT-Based Generation of Planar Graphs, in preparation.

Directed variant of A003094.

Cf. A000273, A003085, A361366

A361578 Number of 5-connected polyhedra (or 5-connected simple planar graphs) with n nodes.

Original entry on oeis.org

1, 0, 1, 1, 5, 8, 30, 85, 382, 1550, 7352

Offset: 12

Manfred Scheucher, Mar 16 2023

The icosahedral graph is the smallest 5-connected planar graph.

M. Kirchweger, M. Scheucher, and S. Szeider, SAT-Based Generation of Planar Graphs, in preparation.

Mathematics Stack Exchange -- What is the smallest 5-vertex-connected (5-edge-connected) planar graph?

Cf. A086216, A005470, A003094, A021103, A000944, A007027.

Cf. A049373 (planar graphs with minimum degree~5) and A111358 (5-connected planar trianguations)

cp's OEIS Frontend

A343873 Triangle read by rows: T(n,k) is the number of unlabeled connected planar graphs with n edges and k nodes (n >= 0, 1 <= k <= n + 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

A049340 Triangle read by rows: T(n,k) is the number of planar graphs with n >= 1 nodes and 0 <= k <= binomial(n,2) edges, all degrees even.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A145270 Number of simple connected nonplanar graphs on n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A243321 Number of simple connected graphs with n nodes that are bipartite and planar.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A298446 Triangle T(n,k) read by rows: number of n-node connected graphs with rectilinear crossing number k (k=0..A014540(n)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A301425 Number of plane 5-regular simple connected graphs with 2n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A307072 Number of simple connected graphs on n nodes with crossing number 1.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A342213 Largest number of maximal planar node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A361368 Number of weakly connected simple planar digraphs with n unlabeled nodes.

Views

Author

Keywords

References

Crossrefs

A361578 Number of 5-connected polyhedra (or 5-connected simple planar graphs) with n nodes.

Views

Author

Keywords