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!)
A006820 Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.
(Formerly M1617)
33
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,8
COMMENTS
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
REFERENCES
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).
LINKS
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.
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.
FORMULA
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
CROSSREFS
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)
Sequence in context: A221841 A068787 A073959 * A131385 A027742 A324062
KEYWORD
nonn,nice,hard
AUTHOR
EXTENSIONS
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
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 April 13 18:34 EDT 2024. Contains 371644 sequences. (Running on oeis4.)