A184963 -id:A184963 - cp's OEIS frontend

A006822 Number of connected regular graphs of degree 6 (or sextic graphs) with n nodes.

1, 0, 0, 0, 0, 0, 0, 1, 1, 4, 21, 266, 7849, 367860, 21609300, 1470293675, 113314233808, 9799685588936, 945095823831036, 101114579937187980, 11945375659139626688, 1551593789610509806552, 220716215902792573134799, 34259321384370620122314325, 5782740798229825207562109439

Offset: 0

N. J. A. Sloane

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.
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 at least g
M. Meringer, Tables of Regular Graphs
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Regular Graph
Eric Weisstein's World of Mathematics, Sextic Graph

Contribution (almost all) from Jason Kimberley, Feb 10 2011: (Start)
6-regular simple graphs: this sequence (connected), A165656 (disconnected), A165627 (not necessarily connected).
Connected regular graphs A005177 (any degree), A068934 (triangular array), specified degree k: A002851 (k=3), A006820 (k=4), A006821 (k=5), this sequence (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).
Connected 6-regular simple graphs with girth at least g: this sequence (g=3), A058276 (g=4).
Connected 6-regular simple graphs with girth exactly g: A184963 (g=3), A184964 (g=4). (End)

a(n) = A184963(n) + A058276(n).
a(n) = A165627(n) - A165656(n).
This sequence is the inverse Euler transformation of A165627.

a(16) and a(17) appended, from running M. Meringer's GENREG at U. Newcastle for 41 processor days and 3.5 processor years, by Jason Kimberley, Sep 04 2009 and Nov 13 2009.

Terms a(18)-a(24), due to the extension of A165627 by Andrew Howroyd, from Jason Kimberley, Mar 12 2020

A014377 Number of connected regular graphs of degree 7 with 2n nodes.

Original entry on oeis.org

1, 0, 0, 0, 1, 5, 1547, 21609301, 733351105934, 42700033549946250, 4073194598236125132578, 613969628444792223002008202, 141515621596238755266884806115631

Offset: 0

N. J. A. Sloane

			a(0)=1 because the null graph (with no vertices) is vacuously 7-regular and connected.

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.

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g
M. Meringer, Tables of Regular Graphs
Eric Weisstein's World of Mathematics, Regular Graph
Eric Weisstein's World of Mathematics, Septic Graph

Contribution (almost all) from Jason Kimberley, Feb 10 2011: (Start)
7-regular simple graphs: this sequence (connected), A165877 (disconnected), A165628 (not necessarily connected).
Connected regular simple graphs A005177 (any degree), A068934 (triangular array), specified degree k: A002851 (k=3), A006820 (k=4), A006821 (k=5), A006822 (k=6), this sequence (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).
Connected 7-regular simple graphs with girth at least g: this sequence (g=3), A181153 (g=4).
Connected 7-regular simple graphs with girth exactly g: A184963 (g=3), A184964 (g=4), A184965 (g=5). (End)

a(n) = A184973(n) + A181153(n).
a(n) = A165628(n) - A165877(n).
This sequence is the inverse Euler transformation of A165628.

Added another term from Meringer's page. Dmitry Kamenetsky, Jul 28 2009
Term a(8) (on Meringer's page) was found from running Meringer's GENREG for 325 processor days at U. Newcastle by Jason Kimberley, Oct 02 2009
a(9)-a(11) from Andrew Howroyd, Mar 13 2020
a(12) from Andrew Howroyd, May 19 2020

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

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 9, 6, 267, 3727, 483012, 69823723, 14836130862

Offset: 0

N. J. A. Sloane, Dec 17 2000

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

Other than at n=0, this sequence first differs from A184964 at n = A054760(6,5) = 40.

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/

6-regular simple graphs with girth at least 4: this sequence (connected), A185264 (disconnected), A185364 (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), A033886 (k=4), A058275 (k=5), this sequence (k=6), A181153 (k=7), A181154 (k=8), A181170 (k=9).
Connected 6-regular simple graphs with girth at least g: A006822 (g=3), this sequence (g=4).
Connected 6-regular simple graphs with girth exactly g: A184963 (g=3), A184964 (g=4).

a(n) = A014377(n) - A184963(n).

Terms a(19), a(20), and a(21), were appended, from running Meringer's GENREG at U. Ncle. for 51 processor days, by Jason Kimberley on Dec 11 2009

a(22) was appended, from running Meringer's GENREG at U. Ncle. for 1620 processor days, by Jason Kimberley on Dec 10 2011

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

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 1, 8, 741, 2887493

Offset: 0

Jason Kimberley, last week of Jan 2011

a(10) was computed by the author in 3 hours using GENREG on Dec 02 2009.

a(11) was computed by the author using GENREG over 45.7 processor days at U. Newcastle from Jan 25 to 27 2011.

			The a(0)=1 null graph is vacuously 7-regular and connected; since it is acyclic then it has infinite girth.
The a(7)=1 graph is the complete bipartite graph K_{7,7} on 14 vertices.
The a(8)=1 graph has girth 4, automorphism group of order 80640, and the following adjacency lists:
01 : 02 03 04 05 06 07 08
02 : 01 09 10 11 12 13 14
03 : 01 09 10 11 12 13 15
04 : 01 09 10 11 12 14 15
05 : 01 09 10 11 13 14 15
06 : 01 09 10 12 13 14 15
07 : 01 09 11 12 13 14 15
08 : 01 10 11 12 13 14 15
09 : 02 03 04 05 06 07 16
10 : 02 03 04 05 06 08 16
11 : 02 03 04 05 07 08 16
12 : 02 03 04 06 07 08 16
13 : 02 03 05 06 07 08 16
14 : 02 04 05 06 07 08 16
15 : 03 04 05 06 07 08 16
16 : 09 10 11 12 13 14 15

M. Meringer, Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory, 30 (1999), 137-146.

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
M. Meringer, Tables of Regular Graphs

7-regular simple graphs with girth at least 4: this sequence (connected), A185274 (disconnected), A185374 (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), A033886 (k=4), A058275 (k=5), A058276 (k=6), this sequence (k=7), A181154 (k=8), A181170 (k=9).
Connected 7-regular simple graphs with girth at least g: A014377 (g=3), this sequence (g=4).
Connected 7-regular simple graphs with girth exactly g: A184963 (g=3), A184964 (g=4).

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

A184953 Number of connected 5-regular (or quintic) simple graphs on 2n vertices with girth exactly 3.

Original entry on oeis.org

0, 0, 0, 1, 3, 59, 7847, 3459376, 2585136287, 2807104844073

Offset: 0

Jason Kimberley, Feb 27 2011

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g
Eric Weisstein's World of Mathematics, Girth.
Eric Weisstein's World of Mathematics, Quintic Graph.

Connected k-regular simple graphs with girth exactly 3: A006923 (k=3), A184943 (k=4), this sequence (k=5), A184963 (k=6), A184973 (k=7), A184983 (k=8), A184993 (k=9).
Connected 5-regular simple graphs with girth at least g: A006821 (g=3), A058275 (g=4).
Connected 5-regular simple graphs with girth exactly g: this sequence (g=3), A184954 (g=4), A184955 (g=5).

a(n) = A006821(n) - A058275(n).

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 9, 6, 267, 3727, 483012, 69823723, 14836130862

Offset: 0

Jason Kimberley, Feb 28 2011

Other than at n=0, this sequence first differs from A058276 at n = A054760(6,5) = 40.

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

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

Connected k-regular simple graphs with girth exactly 4: A006924 (k=3), A184944 (k=4), A184954 (k=5), this sequence (k=6), A184974 (k=7).
Connected 6-regular simple graphs with girth at least g: A006822 (g=3), A058276 (g=4).
Connected 6-regular simple graphs with girth exactly g: A184963 (g=3), this sequence (g=4).

A186733 Triangular array C(n,r) = number of connected r-regular graphs, having girth exactly 3, with n nodes, for 0 <= r < n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 2, 0, 1, 0, 0, 0, 3, 5, 3, 1, 1, 0, 0, 0, 0, 16, 0, 4, 0, 1, 0, 0, 0, 13, 57, 59, 21, 5, 1, 1, 0, 0, 0, 0, 263, 0, 266, 0, 6, 0, 1, 0, 0, 0, 63, 1532, 7847, 7848, 1547, 94, 9, 1, 1, 0, 0, 0, 0, 10747, 0, 367860, 0, 10786

Offset: 1

Jason Kimberley, Mar 26 2012

			01: 0 ;
02: 0, 0 ;
03: 0, 0, 1 ;
04: 0, 0, 0, 1 ;
05: 0, 0, 0, 0, 1 ;
06: 0, 0, 0, 1, 1, 1 ;
07: 0, 0, 0, 0, 2, 0, 1 ;
08: 0, 0, 0, 3, 5, 3, 1, 1 ;
09: 0, 0, 0, 0, 16, 0, 4, 0, 1 ;
10: 0, 0, 0, 13, 57, 59, 21, 5, 1, 1 ;
11: 0, 0, 0, 0, 263, 0, 266, 0, 6, 0, 1 ;
12: 0, 0, 0, 63, 1532, 7847, 7848, 1547, 94, 9, 1, 1 ;
13: 0, 0, 0, 0, 10747, 0, 367860, 0, 10786, 0, 10, 0, 1 ;
14: 0, 0, 0, 399, 87948, 3459376, 21609299, 21609300, 3459386, 88193, 540, 13, 1, 1 ;
15: 0, 0, 0, 0, 803885, 0, 1470293674, 0, 1470293676, 0, 805579, 0, 17, 0, 1 ;
16: 0, 0, 0, 3268, 8020590, 2585136287, 113314233799, 733351105933, 733351105934, 113314233813, 2585136741, 8037796, 4207, 21, 1, 1;

Jason Kimberley, Table of i, a(i)=C(n,r) for i = 1..136 (n = 1..16)
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g

The sum of the n-th row is A186743(n).
Connected k-regular simple graphs with girth exactly 3: this sequence (triangle), A186743 (any k); chosen k: A006923 (k=3), A184943 (k=4), A184953 (k=5), A184963 (k=6), A184973 (k=7), A184983 (k=8), A184993 (k=9).
Triangular arrays C(n,k) counting connected simple k-regular graphs on n vertices with girth *at least* g: A068934 (g=3), A186714 (g=4), A186715 (g=5), A186716 (g=6), A186717 (g=7), A186718 (g=8), A186719 (g=9).
Triangular arrays C(n,k) counting connected simple k-regular graphs on n vertices with girth *exactly* g: this sequence  (g=3), A186734 (g=4).

C(n,r) = A068934(n,r) - A186714(n,r), noting that A186714 has 0 <= r <= n div 2.

A184960 Irregular triangle C(n,g) read by rows, counting the connected 6-regular simple graphs on n vertices with girth exactly g.

Original entry on oeis.org

1, 1, 4, 21, 266, 7848, 1, 367860, 0, 21609299, 1, 1470293674, 1, 113314233799, 9, 9799685588930, 6

Offset: 7

Jason Kimberley, Feb 24 2011

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

			Triangle begins:
1;
1;
4;
21;
266;
7848, 1;
367860, 0;
21609299, 1;
1470293674, 1;
113314233799, 9;
9799685588930, 6;
?, 267;
?, 3727;
?, 483012;
?, 69823723;
?, 14836130862;
The C(40,5)=1 (see the a-file) graph, the unique (6,5)-cage, is the complement of a Petersen graph inside the Hoffman-Singleton graph [from Brouwer link].
The first known of C(42,5)>=1 graph(s) has automorphism group of order 5040 and these adjacency lists:
1 : 2 3 4 5 6 7
2 : 1 8 9 10 11 12
3 : 1 13 14 15 16 17
4 : 1 18 19 20 21 22
5 : 1 23 24 25 26 27
6 : 1 28 29 30 31 32
7 : 1 33 34 35 36 37
8 : 2 13 18 23 28 38
9 : 2 14 19 24 33 39
10 : 2 15 20 29 34 40
11 : 2 16 25 30 35 41
12 : 2 21 26 31 36 42
13 : 3 8 21 27 34 41
14 : 3 9 26 28 37 40
15 : 3 10 22 25 31 39
16 : 3 11 19 32 36 38
17 : 3 20 23 30 33 42
18 : 4 8 25 32 33 40
19 : 4 9 16 27 29 42
20 : 4 10 17 26 35 38
21 : 4 12 13 30 37 39
22 : 4 15 24 28 36 41
23 : 5 8 17 29 36 39
24 : 5 9 22 30 34 38
25 : 5 11 15 18 37 42
26 : 5 12 14 20 32 41
27 : 5 13 19 31 35 40
28 : 6 8 14 22 35 42
29 : 6 10 19 23 37 41
30 : 6 11 17 21 24 40
31 : 6 12 15 27 33 38
32 : 6 16 18 26 34 39
33 : 7 9 17 18 31 41
34 : 7 10 13 24 32 42
35 : 7 11 20 27 28 39
36 : 7 12 16 22 23 40
37 : 7 14 21 25 29 38
38 : 8 16 20 24 31 37
39 : 9 15 21 23 32 35
40 : 10 14 18 27 30 36
41 : 11 13 22 26 29 33
42 : 12 17 19 25 28 34

Andries E. Brouwer, Cages
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth exactly g
Jason Kimberley, Incomplete table of i, n, g, C(n,g)=a(i) for row n = 7..42

Connected 6-regular simple graphs with girth at least g: A184961 (triangle); chosen g: A006822 (g=3), A058276 (g=4).
Connected 6-regular simple graphs with girth exactly g: this sequence (triangle); chosen g: A184963 (g=3), A184964 (g=4).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth exactly g: A198303 (k=3), A184940 (k=4), A184950 (k=5), this sequence (k=6), A184970 (k=7), A184980 (k=8).

After approximately 390 processor days of computation with genreg, C(41,5)=0.

A184961 Irregular triangle C(n,g) read by rows, counting the connected 6-regular simple graphs on n vertices with girth at least g.

Original entry on oeis.org

1, 1, 4, 21, 266, 7849, 1, 367860, 0, 21609300, 1, 1470293675, 1, 113314233808, 9, 9799685588936, 6

Offset: 7

Jason Kimberley, Jan 10 2012

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

			Triangle begins:
1;
1;
4;
21;
266;
7849, 1;
367860, 0;
21609300, 1;
1470293675, 1;
113314233808, 9;
9799685588936, 6;

Andries E. Brouwer, Cages
Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g

Connected 6-regular simple graphs with girth at least g: this sequence (triangle); chosen g: A006822 (g=3), A058276 (g=4).
Connected 6-regular simple graphs with girth exactly g: A184960 (triangle); chosen g: A184963 (g=3), A184964 (g=4).
Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth at least g: A185131 (k=3), A184941 (k=4), A184951 (k=5), this sequence (k=6), A184971 (k=7), A184981 (k=8).

cp's OEIS Frontend

A006822 Number of connected regular graphs of degree 6 (or sextic graphs) with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A014377 Number of connected regular graphs of degree 7 with 2n nodes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

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

A184953 Number of connected 5-regular (or quintic) simple graphs on 2n vertices with girth exactly 3.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A186733 Triangular array C(n,r) = number of connected r-regular graphs, having girth exactly 3, with n nodes, for 0 <= r < n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A184960 Irregular triangle C(n,g) read by rows, counting the connected 6-regular simple graphs on n vertices with girth exactly g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs