A046091 -id:A046091 - cp's OEIS frontend

A002905 Number of connected graphs with n edges.

1, 1, 1, 3, 5, 12, 30, 79, 227, 710, 2322, 8071, 29503, 112822, 450141, 1867871, 8037472, 35787667, 164551477, 779945969, 3804967442, 19079312775, 98211456209, 518397621443, 2802993986619, 15510781288250, 87765472487659, 507395402140211, 2994893000122118, 18035546081743772, 110741792670074054, 692894304050453139

Offset: 0

N. J. A. Sloane

			a(3) = 3 since the three connected graphs with three edges are a path, a triangle and a "Y".
The first difference between this sequence and A046091 is for n=9 edges where we see K_{3,3}, the well-known "utility graph".

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Max Alekseyev, Table of n, a(n) for n = 0..60
G. A. Baker et al., High-temperature expansions for the spin-1/2 Heisenberg model, Phys. Rev., 164 (1967), 800-817.
Nicolas Borie, The Hopf Algebra of graph invariants, arXiv preprint arXiv:1511.05843 [math.CO], 2015.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Mike Cummings and Adam Van Tuyl, The GeometricDecomposability package for Macaulay2, arXiv:2211.02471 [math.AC], 2022.
Anjan Dutta and Hichem Sahbi, Graph Kernels based on High Order Graphlet Parsing and Hashing, arXiv:1803.00425 [cs.CV], 2018.
Gordon Royle, Small graphs
M. L. Stein and P. R. Stein, Enumeration of Linear Graphs and Connected Linear Graphs up to p = 18 Points. Report LA-3775, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, Oct 1967
Peter Steinbach, Field Guide to Simple Graphs, Volume 4, Part 1 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Polynema.

Column sums of A054924 or equivalently row sums of A054923.
Cf. A000664, A046091 (for connected planar graphs), A275421 (multisets).
Apart from a(3), same as A003089.

A000664 = Cases[Import["https://oeis.org/A000664/b000664.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
Join[{1}, EulerInvTransform[Rest @ A000664]] (* Jean-François Alcover, May 10 2019, updated Mar 17 2020 *)

A000664 and this sequence are an Euler transform pair. - N. J. A. Sloane, Aug 30 2016

More terms from Vladeta Jovovic, Jan 12 2000
More terms from Gordon F. Royle, Jun 05 2003
a(25)-a(26) from Max Alekseyev, Sep 19 2009
a(27)-a(60) from Max Alekseyev, Sep 07 2016

A002840 Number of polyhedral graphs with n edges.

Original entry on oeis.org

1, 0, 1, 2, 2, 4, 12, 22, 58, 158, 448, 1342, 4199, 13384, 43708, 144810, 485704, 1645576, 5623571, 19358410, 67078828, 233800162, 819267086, 2884908430, 10204782956, 36249143676, 129267865144, 462669746182, 1661652306539, 5986979643542

Offset: 6

N. J. A. Sloane

M. B. Dillencourt, Polyhedra of small orders and their Hamiltonian properties. Tech. Rep. 92-91, Info. and Comp. Sci. Dept., Univ. Calif. Irvine, 1992.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
T. R. S. Walsh, personal communication.

C. J. Bouwkamp & N. J. A. Sloane, Correspondence, 1971
A. J. W. Duijvestijn and P. J. Federico, The number of polyhedral (3-connected planar) graphs, Math. Comp. 37 (1981), no. 156, 523-532.
P. J. Federico, Enumeration of polyhedra: the number of 9-hedra, J. Combin. Theory, 7 (1969), 155-161.
G. P. Michon, Counting Polyhedra - Numericana
Hugo Pfoertner, Unlabeled 3-connected planar graphs for n<=20 edges, list in PARI-readable format.
Eric Weisstein's World of Mathematics, Polyhedral Graph
T. R. S. Walsh, Number of sensed planar maps with n edges and m vertices

Column sums of A049337.

Cf. A002841, A000944, A046091, A338511, A343869, A343871.

\\ It is assumed that the 3cp.gp file (from the linked zip archive) has been read before, i.e., \r [path]3cp.gp
for(k=6,#ThreeConnectedData,print1(#ThreeConnectedData[k],", "));
\\ printing of the edge lists of the graphs for n <= 11
print(ThreeConnectedData[6..11]) \\ Hugo Pfoertner, Feb 14 2021

a(30)-a(35) from the Numericana link added by Andrey Zabolotskiy, Jun 13 2020

A049334 Triangle read by rows: T(n, k) is the number of unlabeled connected planar simple graphs with n >= 1 nodes and 0<=k<=3*n-6 edges.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 1, 1, 0, 0, 0, 0, 3, 5, 5, 4, 2, 1, 0, 0, 0, 0, 0, 6, 13, 19, 22, 19, 13, 5, 2, 0, 0, 0, 0, 0, 0, 11, 33, 67, 107, 130, 130, 96, 51, 16, 5, 0, 0, 0, 0, 0, 0, 0, 23, 89, 236, 486, 804, 1112, 1211, 1026, 626, 275, 72, 14, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Brendan McKay

Planar graphs with n >= 3 nodes have at most 3*n-6 edges.

			n\k 0  1  2  3  4  5  6  7  8  9 10 11 12
--:-- -- -- -- -- -- -- -- -- -- -- -- --
1:  1
2:  0  1
3:  0  0  1  1
4:  0  0  0  2  2  1  1
5:  0  0  0  0  3  5  5  4  2  1
6:  0  0  0  0  0  6 13 19 22 19 13  5  2

Georg Grasegger, Table of n, a(n) for n = 1..235 (rows 1..13) (terms n = 1..147 (rows 1..11) from Andrew Howroyd)
F. Harary, The number of linear, directed, rooted, and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 445-463. (MR0068198) See page 457, equation (2.9).

Row sums are A003094.
Column sums are A046091.
Cf. A000055, A039735, A049336, A049337, A054924, A288265, A343873 (transpose).

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

T(n, n-1) = A000055(n) and Sum_{k} T(n, k) = A003094(n) if n>=1. - Michael Somos, Aug 23 2015

log(1 + B(x, y)) = Sum{n>0} A(x^n, y^n) / n where A(x, y) = Sum_{n>0, k>=0} T(n,k) * x^n * y^k and similarly B(x, y) with A039735. - Michael Somos, Aug 23 2015

A343869 Number of unlabeled nonseparable (or 2-connected) planar graphs with n edges.

Original entry on oeis.org

1, 0, 1, 1, 2, 4, 7, 16, 41, 108, 320, 1042, 3575, 13064, 49938, 197729, 805991, 3363084, 14302891, 61813285, 270805177, 1200460492, 5376709415, 24302430375, 110745093999, 508380790741

Offset: 1

Andrew Howroyd, May 04 2021

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

Brendan McKay and Adolfo Piperno, nauty and Traces

Row sums of A343870.
Column sums of A049336(n > 1).
Cf. A002840 (3-connected), A010355, A021103, A046091, A289471, A291841.

# count graphs for the sequence by number of vertices v, sum over v afterwards
geng -C $v $n:$n | planarg -q | countg -q # Georg Grasegger, Jun 05 2023

a(21)-a(26) added by Georg Grasegger, Jun 05 2023

A066951 Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges.

Original entry on oeis.org

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008

Offset: 1

Les Reid, May 25 2002

K_4 can't be so drawn even though it is planar. These graphs are a subset of those counted in A046091.

			Up to five edges, every planar graph can be drawn with edges of length 1, so up to this point the sequence agrees with A046091 (connected planar graphs with n edges) [except for the fact that that sequence begins with no edges]. For six edges, the only graphs that cannot be drawn with edges of length 1 are K_4 and K_{3,2}. According to A046091, there are 30 connected planar graphs with 6 edges, so the sixth term is 28.

M. Gardner, The Unexpected Hanging and Other Mathematical Diversions. Simon and Schuster, NY, 1969, p. 80.
R. C. Read, From Forests to Matches, Journal of Recreational Mathematics, Vol. 1:3 (Jul 1968), 60-172.

Jean-Paul Delahaye, Les graphes-allumettes, (in French), Pour la Science no. 445, November 2014.
Raffaele Salvia, A catalogue of matchstick graphs, arXiv:1303.5965 [math.CO], 2013-2015.
Alexis Vaisse, Matchstick graphs
Stefan Vogel and Mike Winkler, Matchstick Graphs Calculator (MGC), a web application for the construction and calculation of unit distance graphs and matchstick graphs.
Eric Weisstein's World of Mathematics, Matchstick Graph

Cf. A003055, A002905, A046091.

a(7) = 70. - Jonathan Vos Post, Jan 05 2007
Corrected, extended and reference added. a(7)=74 and a(8)=207 from Read's paper. - William Rex Marshall, Nov 16 2010
a(9) from Salvia's paper added by Brendan McKay, Apr 13 2013
a(9) corrected (from version 2 [May 22 2013] of Salvia's paper) by Gaetano Ricci, May 24 2013
a(10) from Vaisse's webpage added by Raffaele Salvia, Jan 31 2015

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

Original entry on oeis.org

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

A181528 Number of connected graphs with n edges embeddable into square lattice.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 14, 28, 68, 156, 399, 1012, 2732, 7385, 20665, 58377, 168119, 488771

Offset: 0

I. E. Kashuba (kashuba(AT)bitp.kiev.ua), Oct 27 2010

a(n) <= number of connected planar graphs with n edges A046091.

			For n = 3 there are a(3) = 2 graphs: the claw graph, corresponding to a single free polystick, and the 3-path, corresponding to 4 different free polysticks.

Andreas R. Hehn, Series Expansion Methods for Quantum Lattice Models, Doctoral Thesis, ETH Zürich, 2016.

Cf. A046091, A019988 (embeddings, or free polysticks), A255539 (with n nodes, neighbors connected).

Terms a(16)-a(17) from Hehn Table 3.1 and a(0) = 1 added by Andrey Zabolotskiy, Oct 22 2022

A176425 Number of connected planar graphs with at most n edges.

Original entry on oeis.org

1, 2, 3, 6, 11, 23, 53, 132, 359, 1068, 3386, 11435, 40807, 152807, 597662, 2430734, 10237458, 44489603, 198831994, 911063459

Offset: 0

Jonathan Vos Post, Apr 17 2010

Partial sums of number of connected planar graphs with n edges (A046091).

Table of n, a(n) for n = 0..19

Cf. A002905, A066951, A046091.

a(n) = Sum_{i=0..n} A046091(i).

New name from Bartlomiej Pawlik, May 31 2022

A343872 Number of planar graphs with n edges and no isolated nodes.

Original entry on oeis.org

1, 1, 2, 5, 11, 26, 68, 177, 497, 1475, 4608, 15188, 52778, 192339, 733676, 2917722, 12052138, 51517308, 227068741, 1028492568

Offset: 0

Andrew Howroyd, May 05 2021

The first difference between this sequence and A000664 is for n=9 edges where we see K_{3,3}, the "utility graph".

Cf. A000664, A005470, A039735, A046091.

A046091 = Cases[Import["https://oeis.org/A046091/b046091.txt", "Table"], {, }][[All, 2]];
etr[f_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d f[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];
a = etr[A046091[[# + 1]]&];
a /@ Range[0, Length[A046091]-1] (* Jean-François Alcover, Jan 01 2022 *)

Euler transform of A046091.

cp's OEIS Frontend

A002905 Number of connected graphs with n edges.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A002840 Number of polyhedral graphs with n edges.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A049334 Triangle read by rows: T(n, k) is the number of unlabeled connected planar simple graphs with n >= 1 nodes and 0<=k<=3*n-6 edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

A343869 Number of unlabeled nonseparable (or 2-connected) planar graphs with n edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Extensions

A066951 Number of nonisomorphic connected graphs that can be drawn in the plane using n unit-length edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

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

A181528 Number of connected graphs with n edges embeddable into square lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A176425 Number of connected planar graphs with at most n edges.

Views

Author

Keywords

Comments

Links

Crossrefs