A014375 -id:A014375

A002851

Number of unlabeled trivalent (or cubic) connected simple graphs with 2n nodes.
(Formerly M1521 N0595)

+10
59

1, 0, 1, 2, 5, 19, 85, 509, 4060, 41301, 510489, 7319447, 117940535, 2094480864, 40497138011, 845480228069, 18941522184590, 453090162062723, 11523392072541432, 310467244165539782, 8832736318937756165

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 647.

F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 195.

R. C. Read, Some applications of computers in graph theory, in L. W. Beineke and R. J. Wilson, editors, Selected Topics in Graph Theory, Academic Press, NY, 1978, pp. 417-444.

R. C. Read and G. F. Royle, Chromatic roots of families of graphs, pp. 1009-1029 of Y. Alavi et al., eds., Graph Theory, Combinatorics and Applications. Wiley, NY, 2 vols., 1991.

R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.

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)

LINKS

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

Peter Adams, Ryan C. Bunge, Roger B. Eggleton, Saad I. El-Zanati, Uğur Odabaşi, and Wannasiri Wannasit, Decompositions of complete graphs and complete bipartite graphs into bipartite cubic graphs of order at most 12, Bull. Inst. Combinatorics and Applications (2021) Vol. 92, 50-61.

G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80

G. Brinkmann, J. Goedgebeur, and N. Van Cleemput, The history of the generation of cubic graphs, Int. J. Chem. Modeling 5 (2-3) (2013) 67-89

F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, Computer investigations of cubic graphs, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.

F. C. Bussemaker, S. Cobeljic, D. M. Cvetkovic, and J. J. Seidel, Cubic graphs on <= 14 vertices J. Combinatorial Theory Ser. B 23(1977), no. 2-3, 234--235. MR0485524 (58 #5354).

Timothy B. P. Clark and Adrian Del Maestro, Moments of the inverse participation ratio for the Laplacian on finite regular graphs, arXiv:1506.02048 [math-ph], 2015.

Jan Goedgebeur and Patric R. J. Ostergard, Switching 3-Edge-Colorings of Cubic Graphs, arXiv:2105:01363 [math.CO], May 2021. See Table 1.

H. Gropp, Enumeration of regular graphs 100 years ago, Discrete Math., 101 (1992), 73-85.

House of Graphs, Cubic graphs

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

M. Klin, M. Rücker, Ch. Rücker and G. Tinhofer, Algebraic Combinatorics [broken link]

M. Klin, M. Rücker, Ch. Rücker, and G. Tinhofer, Algebraic Combinatorics (1997)

Denis S. Krotov and Konstantin V. Vorob'ev, On unbalanced Boolean functions attaining the bound 2n/3-1 on the correlation immunity, arXiv:1812.02166 [math.CO], 2018.

R. J. Mathar/Wikipedia, Table of simple cubic graphs [From N. J. A. Sloane, Feb 28 2012]

M. Meringer, Tables of Regular Graphs

R. W. Robinson and N. C. Wormald, Numbers of cubic graphs. J. Graph Theory 7 (1983), no. 4, 463-467.

Sage, Common Graphs (Graph Generators)

J. J. Seidel, R. R. Korfhage, & N. J. A. Sloane, Correspondence 1975

H. M. Sultan, Separating pants decompositions in the pants complex.

H. M. Sultan, Net of Pants Decompositions Containing a non-trivial Separating Curve in the Pants Complex, arXiv:1106.1472 [math.GT], 2011.

Eric Weisstein's World of Mathematics, Connected Graph

Eric Weisstein's World of Mathematics, Cubic Graph

EXAMPLE

G.f. = 1 + x^2 + 2*x^3 + 5*x^4 + 19*x^5 + 85*x^6 + 509*x^7 + 4060*x^8 + 41302*x^9 + 510489*x^10 + 7319447*x^11 + ...

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

a(1) = 0 because there are no simple connected cubic graphs with 2 nodes.

a(2) = 1 because the tetrahedron is the only cubic graph with 4 nodes.

a(3) = 2 because there are two simple cubic graphs with 6 nodes: the bipartite graph K_{3,3} and the triangular prism graph.

CROSSREFS

Cf. A004109 (labeled connected cubic), A361407 (rooted connected cubic), A321305 (signed connected cubic), A000421 (connected cubic loopless multigraphs), A005967 (connected cubic multigraphs), A275744 (multisets).

Contribution (almost all) from Jason Kimberley, Feb 10 2011: (Start)

3-regular simple graphs: this sequence (connected), A165653 (disconnected), A005638 (not necessarily connected), A005964 (planar).

Connected regular graphs A005177 (any degree), A068934 (triangular array), specified degree k: this sequence (k=3), A006820 (k=4), A006821 (k=5), A006822 (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).

Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: this sequence (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

KEYWORD

nonn,nice,changed

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Ronald C. Read

STATUS

approved

A014371

Number of trivalent connected simple graphs with 2n nodes and girth at least 4.

+10
27

1, 0, 0, 1, 2, 6, 22, 110, 792, 7805, 97546, 1435720, 23780814, 432757568, 8542471494, 181492137812, 4127077143862

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

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

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 647.

LINKS

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

G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of Cubic graphs, Discrete Mathematics and Theoretical Computer Science, 13 (2) (2011), 69-80. (hal-00990486)

House of Graphs, Cubic graphs.

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.

M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146.

MATHEMATICA

A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {_, _}][[All, 2]]];

A002851 = A@002851;

A006923 = A@006923;

a[n_] := A002851[[n + 1]] - A006923[[n + 1]];

a /@ Range[0, 16] (* Jean-François Alcover, Jan 27 2020 *)

CROSSREFS

Contribution from Jason Kimberley, Jun 28 2010 and Jan 29 2011: (Start)

3-regular simple graphs with girth at least 4: this sequence (connected), A185234 (disconnected), A185334 (not necessarily connected).

Connected k-regular simple graphs with girth at least 4: A186724 (any k), A186714 (triangle); specified degree k: A185114 (k=2), this sequence (k=3), A033886 (k=4), A058275 (k=5), A058276 (k=6), A181153 (k=7), A181154 (k=8), A181170 (k=9).

Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), this sequence (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

KEYWORD

nonn,nice,more,hard

AUTHOR

N. J. A. Sloane

EXTENSIONS

Terms a(14) and a(15) appended, from running Meringer's GENREG for 4.2 and 93.2 processor days at U. Newcastle, by Jason Kimberley on Jun 28 2010.

a(16), from House of Graphs, by Jan Goedgebeur et al., added by Jason Kimberley, Feb 15 2011

STATUS

approved

A014372

Number of trivalent connected simple graphs with 2n nodes and girth at least 5.

+10
21

1, 0, 0, 0, 0, 1, 2, 9, 49, 455, 5783, 90938, 1620479, 31478584, 656783890, 14621871204, 345975648562

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,7

COMMENTS

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

Brendan McKay has observed that a(13) = 31478584 is output by genreg, minibaum, and snarkhunter, but Meringer's table currently has a(13) = 31478582. - Jason Kimberley, May 17 2017

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 647.

LINKS

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

G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80.

House of Graphs, Cubic graphs.

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

M. Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146.

CROSSREFS

Contribution from Jason Kimberley, 2010, 2011, and 2012: (Start)

3-regular simple graphs with girth at least 5: this sequence (connected), A185235 (disconnected), A185335 (not necessarily connected).

Connected k-regular simple graphs with girth at least 5: A186725 (all k), A186715 (triangle); A185115 (k=2), this sequence (k=3), A058343 (k=4), A205295 (g=5).

Connected 3-regular simple graphs with girth at least g: A185131 (triangle); A002851 (g=3), A014371 (g=4), this sequence (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

KEYWORD

nonn,more,hard

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Terms a(15) and a(16) appended, from running Meringer's GENREG for 28.7 and 715.2 processor days at U. Ncle., by Jason Kimberley, Jun 28 2010.

STATUS

approved

A014374

Number of trivalent connected simple graphs with 2n nodes and girth at least 6.

+10
20

1, 0, 0, 0, 0, 0, 0, 1, 1, 5, 32, 385, 7574, 181227, 4624501, 122090544, 3328929954, 93990692595, 2754222605376

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,10

COMMENTS

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

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 647.

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

LINKS

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

House of Graphs, Cubic graphs

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]

CROSSREFS

From Jason Kimberley, May 18 2010 and 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), this sequence (k=3), A058348 (k=4).

Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), A014371 (g=4), A014372 (g=5), this sequence (g=6), A014375 (g=7), A014376 (g=8).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

KEYWORD

nonn,more,hard

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Terms a(16) and a(17) appended, from running Meringer's GENREG for 18.6 and 530 processor days at U. Ncle., by Jason Kimberley on May 18 2010

Term a(18) from House of Graphs via Jason Kimberley, May 21 2017

STATUS

approved

A006923

Number of connected trivalent graphs with 2n nodes and with girth exactly 3.
(Formerly M2944)

+10
18

0, 0, 1, 1, 3, 13, 63, 399, 3268, 33496, 412943, 5883727, 94159721, 1661723296, 31954666517, 663988090257, 14814445040728

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

REFERENCES

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

LINKS

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

F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, Computer investigations of cubic graphs, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.

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

FORMULA

a(n) = A002851(n) - A014371(n).

CROSSREFS

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); specified g: this sequence (g=3), A006924 (g=4), A006925 (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).

KEYWORD

nonn,hard,more

AUTHOR

N. J. A. Sloane

EXTENSIONS

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

Terms a(14), a(15), and a(16) appended using "new" terms of A014371 by Jason Kimberley, Nov 16 2011

STATUS

approved

A006924

Number of connected trivalent graphs with 2n nodes and girth exactly 4.
(Formerly M1526)

+10
18

0, 0, 0, 1, 2, 5, 20, 101, 743, 7350, 91763, 1344782, 22160335, 401278984, 7885687604, 166870266608, 3781101495300

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

REFERENCES

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

LINKS

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

F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, Computer investigations of cubic graphs, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.

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

FORMULA

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

CROSSREFS

Connected k-regular simple graphs with girth exactly 4: this sequence (k=3), A184944 (k=4), A184954 (k=5), A184964 (k=6), A184974 (k=7).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); specified g: A006923 (g=3), this sequence (g=4), A006925 (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).

KEYWORD

nonn,hard,more

AUTHOR

N. J. A. Sloane.

EXTENSIONS

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

STATUS

approved

A014376

Number of trivalent connected simple graphs with 2n nodes and girth at least 8.

+10
18

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 3, 13, 155, 4337, 266362, 20807688

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,19

REFERENCES

CRC Handbook of Combinatorial Designs, 1996, p. 647.

M. Meringer, Fast Generation of Regular Graphs and Construction of Cages</a>, Journal of Graph Theory, 30 (1999), 137-146 doi 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G [From Jason Kimberley, Jan 29 2011]

LINKS

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

Jason Kimberley, Connected regular graphs with girth at least 8

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

M. Meringer, Tables of Regular Graphs

CROSSREFS

Contribution from Jason Kimberley, May 18 2010 and Jan 29 2011: (Start)

Connected k-regular simple graphs with girth at least 8: A186728 (any k), A186718 (triangle); specific k: A185118 (k=2), this sequence (k=3).

Trivalent simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), this sequence (g=8).

Trivalent simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

KEYWORD

nonn,more,hard

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Terms a(21), a(22), and a(23) found by running Meringer's GENREG for 0.15, 5.0, and 176.2 processor days, respectively, at U. Ncle. by Jason Kimberley, May 18 2010

STATUS

approved

A185131

Irregular triangle C(n,g) counting connected trivalent simple graphs on 2n vertices with girth at least g.

+10
18

1, 2, 1, 5, 2, 19, 6, 1, 85, 22, 2, 509, 110, 9, 1, 4060, 792, 49, 1, 41301, 7805, 455, 5, 510489, 97546, 5783, 32, 7319447, 1435720, 90938, 385, 117940535, 23780814, 1620479, 7574, 1, 2094480864, 432757568, 31478584, 181227, 3, 40497138011, 8542471494

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,2

COMMENTS

The first column is for girth at least 3. The row length is incremented to g-2 when 2n reaches A000066(g).

LINKS

Jason Kimberley, Table of i, a(i) for i = 2..59 (n = 2..16)

B. Brinkmann, J. Goedgebeur, and B. D. McKay, Generation of cubic graphs, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80

House of Graphs, Cubic graphs

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

M. Meringer, Tables of Regular Graphs

EXAMPLE

1;

2, 1;

5, 2;

19, 6, 1;

85, 22, 2;

509, 110, 9, 1;

4060, 792, 49, 1;

41301, 7805, 455, 5;

510489, 97546, 5783, 32;

7319447, 1435720, 90938, 385;

117940535, 23780814, 1620479, 7574, 1;

2094480864, 432757568, 31478584, 181227, 3;

40497138011, 8542471494, 656783890, 4624501, 21;

845480228069, 181492137812, 14621871204, 122090544, 546, 1;

18941522184590, 4127077143862, 345975648562, 3328929954, 30368, 0;

453090162062723, ?, ?, 93990692595, 1782840, 1;

11523392072541432, ?, ?, 2754222605376, 95079083, 3;

310467244165539782, ?, ?, ?, 4686063120, 13;

8832736318937756165, ?, ?, ?, 220323447962, 155;

?, ?, ?, 10090653722861, 4337;

CROSSREFS

Connected 3-regular simple graphs with girth at least g: this sequence (triangle); chosen g: A002851 (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7).

Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth at least g: this sequence (k=3), A184941 (k=4), A184951 (k=5), A184961 (k=6), A184971 (k=7), A184981 (k=8).

KEYWORD

nonn,hard,tabf

AUTHOR

Jason Kimberley, Jan 09 2012

EXTENSIONS

Terms C(18,6), C(20,7) and C(21,7) from House of Graphs via Jason Kimberley, May 21 2017

STATUS

approved

A198303

Irregular triangle C(n,g) counting connected trivalent simple graphs on 2n vertices with girth exactly g.

+10
18

1, 1, 1, 3, 2, 13, 5, 1, 63, 20, 2, 399, 101, 8, 1, 3268, 743, 48, 1, 33496, 7350, 450, 5, 412943, 91763, 5751, 32, 5883727, 1344782, 90553, 385, 94159721, 22160335, 1612905, 7573, 1, 1661723296, 401278984, 31297357, 181224, 3, 31954666517

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,4

COMMENTS

The first column is for girth exactly 3. The row length is incremented to g-2 when 2n reaches A000066(g).

LINKS

Table of n, a(n) for n=2..43.

F. C. Bussemaker, S. Cobeljic, L. M. Cvetkovic and J. J. Seidel, Computer investigations of cubic graphs, T.H.-Report 76-WSK-01, Technological University Eindhoven, Dept. Mathematics, 1976.

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

EXAMPLE

1;

1, 1;

3, 2;

13, 5, 1;

63, 20, 2;

399, 101, 8, 1;

3268, 743, 48, 1;

33496, 7350, 450, 5;

412943, 91763, 5751, 32;

5883727, 1344782, 90553, 385;

94159721, 22160335, 1612905, 7573, 1;

1661723296, 401278984, 31297357, 181224, 3;

31954666517, 7885687604, 652159389, 4624480, 21;

663988090257, 166870266608, 14499780660, 122089998, 545;

14814445040728, 3781101495300, 342646718608, 3328899586, 30368;

CROSSREFS

The sum of the n-th row of this sequence is A002851(n).

Connected 3-regular simple graphs with girth exactly g: this sequence (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7).

Connected 3-regular simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).

Triangular arrays C(n,g) counting connected simple k-regular graphs on n vertices with girth exactly g: this sequence (k=3), A184940 (k=4), A184950 (k=5), A184960 (k=6), A184970 (k=7), A184980 (k=8).

KEYWORD

nonn,hard,tabf

AUTHOR

Jason Kimberley, Nov 16 2011

STATUS

approved

A006925

Number of connected trivalent graphs with 2n nodes and girth exactly 5.
(Formerly M1879)

+10
16

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,7

REFERENCES

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

LINKS

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

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

FORMULA

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

CROSSREFS

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

KEYWORD

nonn,hard,more

AUTHOR

N. J. A. Sloane.

EXTENSIONS

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

STATUS

approved