A085549 -id:A085549 - cp's OEIS frontend

A006820 Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.

1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 59, 265, 1544, 10778, 88168, 805491, 8037418, 86221634, 985870522, 11946487647, 152808063181, 2056692014474, 29051272833609, 429668180677439, 6640165204855036, 107026584471569605, 1796101588825595008, 31333997930603283531, 567437240683788292989

Offset: 0

N. J. A. Sloane

The null graph on 0 vertices is vacuously connected and 4-regular. - Jason Kimberley, Jan 29 2011
The Multiset Transform of this sequence gives a triangle which gives in row n and column k the 4-regular simple graphs with n>=1 nodes and k>=1 components (row sums A033301), starting:
;
;
;
;
1 ;
1 ;
2 ;
6 ;
16 ;
59 1 ;
265 1 ;
1544 3 ;
10778 8 ;
88168 25 ;
805491 87 1 ;
8037418 377 1 ;
86221634 2023 3 ;
985870522 13342 9 ;
11946487647 104568 27 ;
152808063181 930489 96 1 ;  - R. J. Mathar, Jun 02 2022

CRC Handbook of Combinatorial Designs, 1996, p. 648.
I. A. Faradzev, Constructive enumeration of combinatorial objects, pp. 131-135 of Problèmes combinatoires et théorie des graphes (Orsay, 9-13 Juillet 1976). Colloq. Internat. du C.N.R.S., No. 260, Centre Nat. Recherche Scient., Paris, 1978.
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasserasr, Brendan Rooney, and Michael Tait, Regular Graphs of Degree at most Four that Allow Two Distinct Eigenvalues, arXiv:2305.10562 [math.CO], 2023. See p. 7.
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g
M. Meringer, Tables of Regular Graphs
M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146. [_Jason Kimberley_, Nov 24 2009]
M. Meringer, GenReg, Generation of regular graphs, program.
Markus Meringer, H. James Cleaves, Stephen J. Freeland, Beyond Terrestrial Biology: Charting the Chemical Universe of α-Amino Acid Structures, Journal of Chemical Information and Modeling, 53.11 (2013), pp. 2851-2862.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Quartic Graph
Eric Weisstein's World of Mathematics, Regular Graph
Zhipeng Xu, Xiaolong Huang, Fabian Jimenez, and Yuefan Deng, A new record of enumeration of regular graphs by parallel processing, arXiv:1907.12455 [cs.DM], 2019.

From Jason Kimberley, Mar 27 2010 and Jan 29 2011: (Start)
4-regular simple graphs: this sequence (connected), A033483 (disconnected), A033301 (not necessarily connected).
Connected regular simple graphs: A005177 (any degree), A068934 (triangular array); specified degree k: A002851 (k=3), this sequence (k=4), A006821 (k=5), A006822 (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).
Connected 4-regular simple graphs with girth at least g: this sequence (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: A184943 (g=3), A184944 (g=4), A184945 (g=5).
Connected 4-regular graphs: this sequence (simple), A085549 (multigraphs with loops allowed), A129417  (multigraphs with loops verboten). (End)

a(n) = A184943(n) + A033886(n).
a(n) = A033301(n) - A033483(n).
Inverse Euler transform of A033301.
Row sums of A184940. - R. J. Mathar, May 30 2022

a(19)-a(22) were appended by Jason Kimberley on Sep 04 2009, Nov 24 2009, Mar 27 2010, and Mar 18 2011, from running M. Meringer's GENREG for 3.4, 44, and 403 processor days, and 15.5 processor years, at U. Ncle.

a(22) corrected and a(23)-a(28) from Andrew Howroyd, Mar 10 2020

A005967 Number of isomorphism classes of connected 3-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

2, 5, 17, 71, 388, 2592, 21096, 204638, 2317172, 30024276, 437469859, 7067109598, 125184509147, 2410455693765, 50101933643655, 1117669367609605, 26629298567576331, 674793598023809924, 18119844622209998036

Offset: 1

N. J. A. Sloane

nonn

a(n) is the number of maximal cells in the moduli space of tropical curves of genus n+1; see Melody Chan (2012) reference. a(n) is also the number of maximally degenerate stable nodal algebraic curves of genus n+1, up to isomorphism, by the association of a stable nodal curve to its dual graph. - Harry Richman, Oct 23 2023

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 92.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. Brinkmann, N. Van Cleemput, and T. Pisanski, Generation of various classes of trivalent graphs, Theor. Comput. Sci. 502 (2013) 16-29, Table 1 column LM.
Melody Chan, Combinatorics of the tropical Torelli map, Algebra Number Theory, 6 (2012), 1133-1169.
Melody Chan, Moduli Spaces of Curves: Classical and Tropical, Notices Amer. Math. Soc., 68 (2021), 1700-1713.
R. de Mello Koch and S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007 (D7).
R. J. Mathar, Cubic Multigraphs A005967
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019).
Brendan McKay, nauty software
Wikipedia, Moduli of algebraic curves.

Column k=3 of A333397.

Cf. A129427 (Euler transf.), A000421 (no loops), A085549, A129430, A129432, A129434, A129436.

Inverse Euler transform of A129427.

Checked by Brendan McKay, Apr 15 2007
Using sequence A129427, terms a(12)-a(16) were computed in GAP by Ignat Soroko, Apr 07 2010
a(17)-a(19) added by Andrew Howroyd, Mar 19 2020

A129429 Number of isomorphism classes of 4-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 7, 20, 56, 187, 654, 2705, 12587, 67902, 417065, 2897432, 22382255, 189930004, 1750561160, 17380043136, 184653542135, 2088649831822, 25046462480066, 317295911519901, 4233450347175663, 59329632953577985, 871281036897298464

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Equation (5.8) of Read's paper tells us a(n) = N {S_n[S_4] * S_{2n}[S_2]}, where we are working with cycle index polynomials. - Jason Kimberley, Oct 05 2009

Andrew Howroyd, Table of n, a(n) for n = 1..40
R. de Mello Koch and S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436.

Column k=4 of A167625.

Cf. A085549 (connected), A129418, A129427, A129431, A129433, A129435, A129437.

Euler transform of A085549. - Andrew Howroyd, Mar 15 2020

Using equation (5.8) of Read's paper, new terms a(17)-a(19) were computed in MAGMA by Jason Kimberley, Oct 05 2009

Four more terms a(20)-a(23) also computed by Jason Kimberley, Nov 09 2009

A129417 Number of isomorphism classes of connected 4-regular loopless multigraphs of order n.

Original entry on oeis.org

1, 0, 1, 1, 3, 6, 19, 50, 204, 832, 4330, 25227, 171886, 1303725, 10959478, 100230117, 989280132, 10455393155, 117701173970, 1405165683359, 17726785643045, 235585551038117, 3289367315407521, 48136794098893837, 736721822918719557, 11768987500655142988

Offset: 0

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Obtained from A129418 by an inverse Euler transform. - R. J. Mathar, Mar 09 2019

Brendan McKay and Adolfo Piperno, Nauty and Traces

Column k=4 of A328682.

Cf. A129418, A085549, A000421, A129419, A129421, A129423, A129425, A328682.

geng -c -d1 ${n} -q | multig -r4 -u # Natan Arie Consigli, Jun 05 2017

a(0)-a(1) prepended by Natan Arie Consigli, Jun 05 2017

a(18)-a(25) from Andrew Howroyd, Mar 17 2020

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

3, 26, 639, 40264, 5846105, 1620621150, 752480161278, 538934691750368, 562620407713724992, 820458681175954269942, 1616087981640640784235446, 4183688192689449962777539596, 13914233045360143936837907106395, 58319096569220501055727735345999221

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=5 of A333397.

Cf. A129431, A129419, A005967, A085549, A129432, A129434, A129436.

Inverse Euler transform of A129431. - Andrew Howroyd, Mar 19 2020

a(8)-a(14) added by Andrew Howroyd, Mar 21 2020

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 2, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1, 1, 3, 4, 5, 1, 0, 0, 1, 0, 3, 0, 10, 0, 1, 0, 0, 1, 1, 4, 9, 26, 28, 17, 1, 0, 0, 1, 0, 4, 0, 47, 0, 97, 0, 1, 0, 0, 1, 1, 5, 17, 91, 291, 639, 359, 71, 1, 0, 0, 1, 0, 5, 0, 149, 0, 2789, 0, 1635, 0, 1, 0, 0

Offset: 0

Andrew Howroyd, Mar 18 2020

This sequence can be derived from A167625 by inverse Euler transform.

			Array begins:
=========================================================
n\k | 0 1 2  3    4     5        6       7          8
----+----------------------------------------------------
  0 | 1 1 1  1    1     1        1       1          1 ...
  1 | 1 0 1  0    1     0        1       0          1 ...
  2 | 0 1 1  2    2     3        3       4          4 ...
  3 | 0 0 1  0    4     0        9       0         17 ...
  4 | 0 0 1  5   10    26       47      91        149 ...
  5 | 0 0 1  0   28     0      291       0       1934 ...
  6 | 0 0 1 17   97   639     2789   12398      44821 ...
  7 | 0 0 1  0  359     0    35646       0    1631629 ...
  8 | 0 0 1 71 1635 40264   622457 8530044   89057367 ...
  9 | 0 0 1  0 8296     0 14019433       0 6849428873 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..405 (first 28 antidiagonals)

Columns k=3..8 (with interspersed 0's for odd k) are: A005967, A085549, A129430, A129432, A129434, A129436.

Cf. A167625 (not necessarily connected), A322115 (not necessarily regular), A328682 (loopless), A333330.

Column k is the inverse Euler transform of column k of A167625.

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 9, 47, 291, 2789, 35646, 622457, 14019433, 395208047, 13561118011, 555498075986, 26751985389463, 1496090275853092, 96154662330195078, 7038800665162854369, 582281978355495520076, 54057819690711609171892, 5597375885970846586170796, 642829784413912305507730345

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=6 of A333397.

Cf. A129433, A129421, A005967, A085549, A129430, A129434, A129436.

Inverse Euler transform of A129433. - Andrew Howroyd, Mar 19 2020

a(13)-a(20) added by Andrew Howroyd, Mar 19 2020

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

4, 91, 12398, 8530044, 20068725095, 122563246940846, 1657847267734501346, 44557979504639651662163, 2193071655191529316254072193, 185380797361862371952777763438426

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=7 of A333397.

Cf. A129435, A129423, A005967, A085549, A129430, A129432, A129436.

Inverse Euler transform of A129435. - Andrew Howroyd, Mar 19 2020

a(6)-a(10) added by Andrew Howroyd, Mar 21 2020

A129436 Number of isomorphism classes of connected 8-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 4, 17, 149, 1934, 44821, 1631629, 89057367, 6849428873, 713780361312, 97876276145119, 17259548258350637, 3840154740252625874, 1060662127742505706789, 358584059544008234423217, 146560585570176100774010071, 71630591614693085251230481320, 41456445821273701849195905028292

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Column k=8 of A333397.

Cf. A129437, A129425, A005967, A085549, A129430, A129432, A129434.

Inverse Euler transform of A129437. - Andrew Howroyd, Mar 19 2020

a(11)-a(18) added by Andrew Howroyd, Mar 21 2020

A361135 The number of unlabeled connected fairly 4-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 8, 30, 118, 548, 2790, 16029, 101353, 706572, 5375249, 44402094, 395734706, 3786401086, 38711834576, 421217184135, 4860174299186, 59278045511959, 762055884150141, 10299293881159294, 145994591873294780, 2165938721141964179, 33564939201581495090, 542344644703485899950, 9122110321170144880053

Offset: 1

R. J. Mathar, Mar 02 2023

Edges are undirected, vertices not labeled. "Fairly" means that each vertex has degree 4, but two of these edges do not connect to a second vertex; they are "fins" in CAD speak or "half-edges" in perturbation theory. The two fins may be attached to the same or to two different nodes. In the usual mathematical nomenclature these are connected graphs of order n+2 with two vertices of degree 1 and n vertices of degree 4, loops allowed.

H. Kleinert, A. Pelster, B. Kastening, and M. Bachmann, Recursive graphical construction of Feynman diagrams and their multiplicities in Phi^4 and Phi^2*A theory, Phys. Rev. E 62 (2) (2000), 1537 Table II.
R. J. Mathar, Illustrations

Cf. A085549 (4-regular), A352174 (assuming rooted external legs).

Terms a(7) and beyond from Andrew Howroyd, Mar 05 2023

cp's OEIS Frontend

A006820 Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A005967 Number of isomorphism classes of connected 3-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A129429 Number of isomorphism classes of 4-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A129417 Number of isomorphism classes of connected 4-regular loopless multigraphs of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Extensions

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A333397 Array read by antidiagonals: T(n,k) is the number of connected k-regular multigraphs on n unlabeled nodes, loops allowed, n >= 0, k >= 0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129436 Number of isomorphism classes of connected 8-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula