A184945 -id:A184945 - 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

A033886 Number of connected 4-regular simple graphs on n vertices with girth at least 4.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 12, 31, 220, 1606, 16828, 193900, 2452818, 32670330, 456028474, 6636066099, 100135577747, 1582718912968

Offset: 0

N. J. A. Sloane, Dec 17 2000

The null graph on 0 vertices is vacuously connected and 4-regular; since it is acyclic, it has infinite girth. - Jason Kimberley, Jan 29 2011

Jason Kimberley, Connected regular graphs with girth at least 4.
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g.
Markus Meringer, Fast Generation of Regular Graphs and Construction of Cages, Journal of Graph Theory, Vol. 30, No. 2 (1999), 137-146.
Markus Meringer, Tables of Regular Graphs.

From Jason Kimberley, Mar 19 2010 and Jan 28 2011: (Start)
4-regular simple graphs with girth at least 4: this sequence (connected), A185244 (disconnected), A185344 (not necessarily connected).
Connected k-regular simple graphs with girth at least 4: A186724 (any k), A186714 (triangle); specified degree k: A185114 (k=2), A014371 (k=3), this sequence (k=4), A058275 (k=5), A058276 (k=6), A181153 (k=7), A181154 (k=8), A181170 (k=9).
Connected 4-regular simple graphs with girth at least g: A006820 (g=3), this sequence (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). (End)

By running M. Meringer's GENREG at U. Newcastle for 6.25, 107 and 1548 processor days, a(21), a(22), and a(23) were completed by Jason Kimberley on Dec 06 2009, Mar 19 2010, and Nov 02 2011.

A006925 Number of connected trivalent graphs with 2n nodes and girth exactly 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 8, 48, 450, 5751, 90553, 1612905, 31297357, 652159389, 14499780660, 342646718608

Offset: 0

N. J. A. Sloane

CRC Handbook of Combinatorial Designs, 1996, p. 647.
Gordon Royle, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

Connected k-regular simple graphs with girth exactly 5: this sequence (k=3), A184945 (k=4), A184955 (k=5).
Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); specified g: A006923 (g=3), A006924 (g=4), this sequence
(g=5), A006926 (g=6), A006927 (g=7).
Connected 3-regular simple graphs with girth at least g: A002851 (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

a(n) = A014372(n) - A014374(n).

Definition corrected to include "connected", and "girth at least 5" minus "girth at least 6" formula provided by Jason Kimberley, Dec 12 2009

A184944 Number of connected 4-regular simple graphs on n vertices with girth exactly 4.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 12, 31, 220, 1606, 16828, 193900, 2452818, 32670329, 456028472, 6636066091, 100135577616, 1582718909051

Offset: 0

Jason Kimberley, Jan 26 2011

			a(0)=0 because even though the null graph (on zero vertices) is vacuously 4-regular and connected, since it is acyclic, it has infinite girth.
The a(8)=1 graph is the complete bipartite graph K_{4,4}.

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

4-regular simple graphs with girth exactly 4: this sequence (connected), A185044 (disconnected), A185144 (not necessarily connected).
Connected k-regular simple graphs with girth exactly 4: A006924 (k=3), this sequence (k=4), A184954 (k=5), A184964 (k=6), A184974 (k=7).
Connected 4-regular simple graphs with girth at least g: A006820 (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: A184943 (g=3), this sequence (g=4), A184945 (g=5).

a(n) = A033886(n) - A058343(n).

a(23) was appended by the author once A033886(23) was known, Nov 03 2011

A058343 Number of connected 4-regular simple graphs on n vertices with girth at least 5.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 8, 131, 3917, 123859, 4131991, 132160608, 4018022149, 118369811960

Offset: 0

N. J. A. Sloane, Dec 17 2000

The null graph on 0 vertices is vacuously connected and 4-regular; since it is acyclic, it has infinite girth. [From Jason Kimberley, Jan 29 2011]

M. Meringer, Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory, 30 (1999), 137-146. [From Jason Kimberley, Jan 29 2011]

Jason Kimberley, Connected regular graphs with girth at least 5
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g
M. Meringer, Tables of Regular Graphs

Contribution from Jason Kimberley, 2010, 2011, and 2012: (Start)
4-regular simple graphs with girth at least 5: this sequence (connected), A185245 (disconnected), A185345 (not necessarily connected).
Connected k-regular simple graphs with girth at least 5: A186725 (all k), A186715 (triangle); A185115 (k=2), A014372 (k=3), this sequence (k=4), A205295 (k=5).
Connected 4-regular simple graphs with girth at least g: A006820 (g=3), A033886 (g=4), this sequence (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: A184943 (g=3), A184944 (g=4), A184945 (g=5). (End)

Terms a(27) and a(28) were appended by Jason Kimberley, from running Meringer's GENREG for 58 and 1563 processor days at U. Ncle, on Mar 19 and Jun 28 2010.

A058348 Number of connected 4-regular simple graphs on n vertices with girth at least 6.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 4, 0, 19, 0, 1272, 25, 494031, 13504

Offset: 0

N. J. A. Sloane, Dec 17 2000

From Jason Kimberley, 2011: (Start)
The null graph on 0 vertices is vacuously connected and 4-regular; since it is acyclic, it has infinite girth.
Does a(2n+1) ever exceed a(2n)?
(End)

Jason Kimberley, Connected regular graphs with girth at least 6
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_, Jan 29 2011]

From Jason Kimberley, Jan 29 2011: (Start)
Connected k-regular simple graphs with girth at least 6: A186726 (any k), A186716 (triangle); specified degree k: A185116 (k=2), A014374 (k=3), this sequence (k=4).
Connected 4-regular simple graphs with girth at least g: A006820 (g=3), A033886 (g=4), A058343 (g=5), this sequence (g=6).
Connected 4-regular simple graphs with girth exactly g: A184943 (g=3), A184944 (g=4), A184945 (g=5). (End)

Jason Kimberley inserted Meringer's computed terms a(n)=0 for n in [27,29,31,33] and appended terms a(35) and a(36), by running Meringer's GENREG for 17 and 106 processor days at U. Ncle, on May 04 2010.

a(37) appended from running GENREG for 450 processor days at U. Ncle. by Jason Kimberley, Dec 03 2011

A184943 Number of connected 4-regular simple graphs on n vertices with girth exactly 3.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 2, 5, 16, 57, 263, 1532, 10747, 87948, 803885, 8020590, 86027734, 983417704, 11913817317, 152352034707, 2050055948375, 28951137255862, 428085461764471

Offset: 0

Jason Kimberley, Jan 25 2011

			a(0)=0 because even though the null graph (on zero vertices) is vacuously 4-regular and connected, since it is acyclic, it has infinite girth.
The a(5)=1 complete graph on 5 vertices is 4-regular; it has 10 edges and 10 triangles.

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

4-regular simple graphs with girth exactly 3: this sequence (connected), A185043 (disconnected), A185143 (not necessarily connected).
Connected k-regular simple graphs with girth exactly 3: A006923 (k=3), this sequence (k=4), A184953 (k=5), A184963 (k=6), A184973 (k=7), A184983 (k=8), A184993 (k=9).
Connected 4-regular simple graphs with girth at least g: A006820 (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: this sequence (g=3), A184944 (g=4), A184945 (g=5).

A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A006820 = A@006820; A033886 = A@033886;
a[n_] := A006820[[n + 1]] - A033886[[n + 1]];
a /@ Range[0, 22] (* Jean-François Alcover, Jan 27 2020 *)

a(n) = A006820(n) - A033886(n).

Term a(22) corrected and a(23) appended, due to the correction and extension of A006820 by Andrew Howroyd, from Jason Kimberley, Mar 13 2020

A184955 Number of connected 5-regular simple graphs on 2n vertices with girth exactly 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 90

Offset: 0

Jason Kimberley, Feb 27 2011

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

Connected k-regular simple graphs with girth exactly 5: A185015 (k=2), A006925 (k=3), A184945 (k=4), this sequence (k=5).
Connected 5-regular simple graphs with girth at least g: A006821 (g=3), A058275 (g=4), A205295 (g=5).
Connected 5-regular simple graphs with girth exactly g: A184953 (g=3), A184954 (g=4), this sequence (g=5).

A184940 Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth exactly g.

Original entry on oeis.org

1, 1, 2, 5, 1, 16, 0, 57, 2, 263, 2, 1532, 12, 10747, 31, 87948, 220, 803885, 1606, 8020590, 16828, 86027734, 193900, 983417704, 2452818, 11913817317, 32670329, 1, 152352034707, 456028472, 2, 2050055948375, 6636066091, 8, 28466137588780, 100135577616, 131

Offset: 5

Jason Kimberley, Feb 24 2011

The first column is for girth exactly 3. The row length sequence starts: 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4. The row length is incremented to g-2 when n reaches A037233(g).

			1;
1;
2;
5, 1;
16, 0;
57, 2;
263, 2;
1532, 12;
10747, 31;
87948, 220;
803885, 1606;
8020590, 16828;
86027734, 193900;
983417704, 2452818;
11913817317, 32670329, 1;
152352034707, 456028472, 2;
2050055948375, 6636066091, 8;
28466137588780, 100135577616, 131;

Jason Kimberley, Incomplete table of i, n, g, C(n,g)=a(i) for row n = 5..36
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

Connected 4-regular simple graphs with girth at least g: A184941 (triangle); chosen g: A006820 (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: this sequence (triangle); chosen g: A184943 (g=3), A184944 (g=4), A184945 (g=5), A184946 (g=6).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth exactly g: A198303 (k=3), this sequence (k=4), A184950 (k=5), A184960 (k=6), A184970 (k=7), A184980 (k=8).

A184941 Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth at least g.

Original entry on oeis.org

1, 1, 2, 6, 1, 16, 0, 59, 2, 265, 2, 1544, 12, 10778, 31, 88168, 220, 805491, 1606, 8037418, 16828, 86221634, 193900, 985870522, 2452818, 11946487647, 32670330, 1, 152808063181, 456028474, 2, 2056692014474, 6636066099, 8, 28566273166527, 100135577747, 131

Offset: 5

Jason Kimberley, Jan 10 2012

The first column is for girth at least 3. The row length sequence starts: 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4. The row length is incremented to g-2 when n reaches A037233(g).

			1;
1;
2;
6, 1;
16, 0;
59, 2;
265, 2;
1544, 12;
10778, 31;
88168, 220;
805491, 1606;
8037418, 16828;
86221634, 193900;
985870522, 2452818;
11946487647, 32670330, 1;
152808063181, 456028474, 2;
2056692014474, 6636066099, 8;
28566273166527, 100135577747, 131;

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g

Connected 4-regular simple graphs with girth at least g: this sequence (triangle); chosen g: A006820 (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: A184940 (triangle); chosen g: A184943 (g=3), A184944 (g=4), A184945 (g=5), A184946 (g=6).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth at least g: A185131 (k=3), this sequence (k=4), A184951 (k=5), A184961 (k=6), A184971 (k=7), A184981 (k=8).

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

A033886 Number of connected 4-regular simple graphs on n vertices with girth at least 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A006925 Number of connected trivalent graphs with 2n nodes and girth exactly 5.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A184944 Number of connected 4-regular simple graphs on n vertices with girth exactly 4.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A058343 Number of connected 4-regular simple graphs on n vertices with girth at least 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A058348 Number of connected 4-regular simple graphs on n vertices with girth at least 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A184943 Number of connected 4-regular simple graphs on n vertices with girth exactly 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A184955 Number of connected 5-regular simple graphs on 2n vertices with girth exactly 5.

Views

Author

Keywords

Links

Crossrefs

A184940 Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth exactly g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A184941 Irregular triangle C(n,g) counting the connected 4-regular simple graphs on n vertices with girth at least g.