Displaying 1-10 of 33 results found.
1, 1, 1, 1, 1, 2, 3, 5, 11, 27, 86, 351, 1895, 12673, 100841, 906332, 8943750, 95165384, 1081035906, 13027523553, 165835586734, 2222527601208, 31273800434817, 460941981112256, 7101107185967292, 114127691657536897, 1910229280483131905, 33244227211086415436
COMMENTS
Number of connected quartic graphs with at most n nodes.
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
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
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).
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). 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).
EXTENSIONS
More terms from Ronald C. Read
Triangular array C(n, r) = number of connected r-regular graphs with n nodes, 0 <= r < n.
+10
31
1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 2, 1, 1, 0, 0, 1, 0, 2, 0, 1, 0, 0, 1, 5, 6, 3, 1, 1, 0, 0, 1, 0, 16, 0, 4, 0, 1, 0, 0, 1, 19, 59, 60, 21, 5, 1, 1, 0, 0, 1, 0, 265, 0, 266, 0, 6, 0, 1, 0, 0, 1, 85, 1544, 7848, 7849, 1547, 94, 9, 1, 1, 0, 0, 1, 0, 10778, 0, 367860, 0
COMMENTS
A graph is called r-regular if every node has exactly r edges. The numbers in this table were copied from the column sequences.
This sequence can be derived from A051031 by inverse Euler transform. See the comments in A051031 for a brief description of how that sequence can be computed without generating all regular graphs. - Andrew Howroyd, Mar 13 2020
EXAMPLE
01: 1;
02: 0, 1;
03: 0, 0, 1;
04: 0, 0, 1, 1;
05: 0, 0, 1, 0, 1;
06: 0, 0, 1, 2, 1, 1;
07: 0, 0, 1, 0, 2, 0, 1;
08: 0, 0, 1, 5, 6, 3, 1, 1;
09: 0, 0, 1, 0, 16, 0, 4, 0, 1;
10: 0, 0, 1, 19, 59, 60, 21, 5, 1, 1;
11: 0, 0, 1, 0, 265, 0, 266, 0, 6, 0, 1;
12: 0, 0, 1, 85, 1544, 7848, 7849, 1547, 94, 9, 1, 1;
13: 0, 0, 1, 0, 10778, 0, 367860, 0, 10786, 0, 10, 0, 1;
14: 0, 0, 1, 509, 88168, 3459383, 21609300, 21609301, 3459386, 88193, 540, 13, 1, 1;
15: 0, 0, 1, 0, 805491, 0, 1470293675, 0, 1470293676, 0, 805579, 0, 17, 0, 1;
16: 0, 0, 1, 4060, 8037418, 2585136675, 113314233808, 733351105934, 733351105935, 113314233813, 2585136741, 8037796, 4207, 21, 1, 1;
CROSSREFS
Connected regular simple graphs: A005177 (any degree -- sum of rows), this sequence (triangular array), specified degree r (columns): A002851 (r=3), A006820 (r=4), A006821 (r=5), A006822 (r=6), A014377 (r=7), A014378 (r=8), A014381 (r=9), A014382 (r=10), A014384 (r=11). Triangular arrays C(n,k) counting connected simple k-regular graphs on n vertices with girth *at least* g: this sequence (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: A186733 (g=3), A186734 (g=4).
Number of connected regular graphs with n nodes.
(Formerly M0347)
+10
29
1, 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, 539, 18979, 389436, 50314796, 2942198440, 1698517036411, 442786966115560, 649978211591600286, 429712868499646474880, 2886054228478618211088773, 8835589045148342277771518309, 152929279364927228928021274993215, 1207932509391069805495173301992815105, 99162609848561525198669168640159162918815
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
FORMULA
a(n) = sum of the n-th row of A068934. This sequence is the inverse Euler transformation of A165647.
CROSSREFS
Regular simple graphs of any degree: this sequence (connected), A068932 (disconnected), A005176 (not necessarily connected), A275420 (multisets). Connected regular simple graphs: this sequence (any degree), A068934 (triangular array); specified degree k: A002851 (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). - Jason Kimberley, Nov 03 2011
EXTENSIONS
Terms are sums of the output from M. Meringer's genreg software. To complete a(16) it was run by Jason Kimberley, Sep 23 2009 a(0)=1 (due to the empty graph being vacuously connected and regular) inserted by Jason Kimberley, Apr 11 2012
Number of connected regular graphs of degree 5 (or quintic graphs) with 2n nodes.
(Formerly M3168)
+10
23
1, 0, 0, 1, 3, 60, 7848, 3459383, 2585136675, 2807105250897, 4221456117363365, 8516994770090547979, 22470883218081146186209, 75883288444204588922998674, 322040154704144697047052726990
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).
FORMULA
Inverse Euler transform of A165626.
EXAMPLE
a(0)=1 because the null graph (with no vertices) is vacuously 5-regular and connected.
CROSSREFS
5-regular simple graphs: this sequence (connected), A165655 (disconnected), A165626 (not necessarily connected). Connected regular simple graphs A005177 (any degree), A068934 (triangular array), specified degree k: A002851 (k=3), A006820 (k=4), this sequence (k=5), A006822 (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11). Connected 5-regular simple graphs with girth at least g: this sequence (g=3), A058275 (g=4), A205295 (g=5). Connected 5-regular graphs: A129430 (loops and multiple edges allowed), A129419 (no loops but multiple edges allowed), this sequence (no loops nor multiple edges). (End)
EXTENSIONS
By running M. Meringer's GENREG for about 2 processor years at U. Newcastle, a(9) was found by Jason Kimberley, Nov 24 2009
Number of connected regular graphs of degree 8 with n nodes.
+10
21
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 6, 94, 10786, 3459386, 1470293676, 733351105935, 423187422492342, 281341168330848873, 214755319657939505395, 187549729101764460261498, 186685399408147545744203815, 210977245260028917322933154987
COMMENTS
Since the nontrivial 8-regular graph with the least number of vertices is K_9, there are no disconnected 8-regular graphs with less than 18 vertices. Thus for n<18 this sequence is identical to A180260. - Jason Kimberley, Sep 25 2009 and Feb 10 2011
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.
FORMULA
This sequence is the inverse Euler transformation of A180260.
EXAMPLE
a(0)=1 because the null graph (with no vertices) is vacuously 8-regular and connected.
CROSSREFS
8-regular simple graphs: this sequence (connected), A165878 (disconnected), A180260 (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), A014377 (k=7), this sequence (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11). Connected 8-regular simple graphs with girth at least g: A184981 (triangle); chosen g: A014378 (g=3), A181154 (g=4). Connected 8-regular simple graphs with girth exactly g: A184980 (triangle); chosen g: A184983 (g=3). (End)
Number of connected regular graphs of degree 6 (or sextic graphs) with n nodes.
(Formerly M3579)
+10
20
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
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
This sequence is the inverse Euler transformation of A165627.
CROSSREFS
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)
EXTENSIONS
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.
Number of connected regular graphs of degree 7 with 2n nodes.
+10
20
1, 0, 0, 0, 1, 5, 1547, 21609301, 733351105934, 42700033549946250, 4073194598236125132578, 613969628444792223002008202, 141515621596238755266884806115631
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.
FORMULA
This sequence is the inverse Euler transformation of A165628.
EXAMPLE
a(0)=1 because the null graph (with no vertices) is vacuously 7-regular and connected.
CROSSREFS
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)
EXTENSIONS
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
Number of connected 4-regular simple graphs on n vertices with girth at least 4.
+10
20
1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 2, 2, 12, 31, 220, 1606, 16828, 193900, 2452818, 32670330, 456028474, 6636066099, 100135577747, 1582718912968
COMMENTS
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
REFERENCES
M. Meringer, Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory, 30 (1999), pp. 137-146.
CROSSREFS
4-regular simple graphs with girth at least 4: this sequence (connected), A185244 (disconnected), A185344 (not necessarily connected). 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)
EXTENSIONS
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.
Number of 4-valent (or quartic) graphs with n nodes.
+10
17
1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 60, 266, 1547, 10786, 88193, 805579, 8037796, 86223660, 985883873, 11946592242, 152808993767, 2056701139136, 29051369533596, 429669276147047, 6640178380127244, 107026751932268789, 1796103830404560857, 31334029441145918974, 567437704731717802783
COMMENTS
Because the triangle A051031 is symmetric, a(n) is also the number of (n-5)-regular graphs on n vertices. - Jason Kimberley, Sep 22 2009
REFERENCES
R. C. Read and R. J. Wilson, An Atlas of Graphs, Oxford, 1998.
LINKS
M. Meringer, Erzeugung Regulaerer Graphen, Diploma thesis, University of Bayreuth, January 1996. [From Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 25 2010] Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
MATHEMATICA
A006820 = Cases[Import["https://oeis.org/ A006820/b006820.txt", "Table"], {_, _}][[All, 2]];
(* EulerTransform is defined in A005195 *)
CROSSREFS
4-regular simple graphs: A006820 (connected), A033483 (disconnected), this sequence (not necessarily connected).
EXTENSIONS
a(16) from Axel Kohnert (kohnert(AT)uni-bayreuth.de), Jul 24 2003
a(20)-a(21) from Herman Jamke (hermanjamke(AT)fastmail.fm), Sep 25 2010
Search completed in 0.025 seconds
| 
