A180260 -id:A180260 - cp's OEIS frontend

A005176 Number of regular graphs with n unlabeled nodes.

1, 1, 2, 2, 4, 3, 8, 6, 22, 26, 176, 546, 19002, 389454, 50314870, 2942198546, 1698517037030, 442786966117636, 649978211591622812, 429712868499646587714, 2886054228478618215888598, 8835589045148342277802657274, 152929279364927228928025482936226, 1207932509391069805495173417972533120, 99162609848561525198669168653641835566774

Offset: 0

N. J. A. Sloane

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

E. Friedman, Illustration of small graphs
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g
Jennifer M. Larson, Cheating Because They Can: Social Networks and Norm Violators, 2014. See Footnote 11.
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.)
Eric Weisstein's World of Mathematics, Regular Graph.

Not necessarily connected simple regular graphs: A005176 (any degree), A051031 (triangular array), specified degree k: A000012 (k=0), A059841 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).
Simple regular graphs of any degree: A005177 (connected), A068932 (disconnected), this sequence (not necessarily connected).
Not necessarily connected regular simple graphs with girth at least g: this sequence (g=3), A185314 (g=4), A185315 (g=5), A185316 (g=6), A185317 (g=7), A185318 (g=8), A185319 (g=9).
Cf. A295193.

a(n) = A005177(n) + A068932(n). - David Wasserman, Mar 08 2002

Row sums of triangle A051031.

More terms from David Wasserman, Mar 08 2002
a(15) and a(16) from Jason Kimberley, Sep 25 2009
Edited by Jason Kimberley, Jan 06 2011 and May 24 2012
a(17)-a(21) from Andrew Howroyd, Mar 08 2020
a(22)-a(24) from Andrew Howroyd, Apr 05 2020

A005638 Number of unlabeled trivalent (or cubic) graphs with 2n nodes.

Original entry on oeis.org

1, 0, 1, 2, 6, 21, 94, 540, 4207, 42110, 516344, 7373924, 118573592, 2103205738, 40634185402, 847871397424, 18987149095005, 454032821688754, 11544329612485981, 310964453836198311, 8845303172513781271

Offset: 0

N. J. A. Sloane

Because the triangle A051031 is symmetric, a(n) is also the number of (2n-4)-regular graphs on 2n vertices.

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

G. Brinkmann, Fast generation of cubic graphs, Journal of Graph Theory, 23(2):139-149, 1996.
Jason Kimberley, Not-necessarily connected regular graphs
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g
R. W. Robinson, Cubic graphs (notes)
Robinson, R. W.; Wormald, N. C., Numbers of cubic graphs, J. Graph Theory 7 (1983), no. 4, 463-467.
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.)
Eric Weisstein's World of Mathematics, Cubic Graph
Gal Weitz, Lirandë Pira, Chris Ferrie, and Joshua Combes, Sub-universal variational circuits for combinatorial optimization problems, arXiv:2308.14981 [quant-ph], 2023.

Cf. A000421.
Row sums of A275744.
3-regular simple graphs: A002851 (connected), A165653 (disconnected), this sequence (not necessarily connected).
Regular graphs A005176 (any degree), A051031 (triangular array), chosen degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), this sequence (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).
Not necessarily connected 3-regular simple graphs with girth *at least* g: this sequence (g=3), A185334 (g=4), A185335 (g=5), A185336 (g=6).
Not necessarily connected 3-regular simple graphs with girth *exactly* g: A185133 (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).

a(n) = A002851(n) + A165653(n).

This sequence is the Euler transformation of A002851.

More terms from Ronald C. Read.

Comment, formulas, and (most) crossrefs by Jason Kimberley, 2009 and 2012

A051031 Triangle read by rows: T(n,r) is the number of not necessarily connected r-regular graphs with n nodes, 0 <= r < n.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 2, 2, 1, 1, 1, 0, 2, 0, 2, 0, 1, 1, 1, 3, 6, 6, 3, 1, 1, 1, 0, 4, 0, 16, 0, 4, 0, 1, 1, 1, 5, 21, 60, 60, 21, 5, 1, 1, 1, 0, 6, 0, 266, 0, 266, 0, 6, 0, 1, 1, 1, 9, 94, 1547, 7849, 7849, 1547, 94, 9, 1, 1, 1, 0, 10, 0, 10786, 0, 367860, 0, 10786

Offset: 1

Eric W. Weisstein

A graph in which every node has r edges is called an r-regular graph. The triangle is symmetric because if an n-node graph is r-regular, than its complement is (n - 1 - r)-regular and two graphs are isomorphic if and only if their complements are isomorphic.

Terms may be computed without generating each graph by enumerating the number of graphs by degree sequence. A PARI program showing this technique for graphs with labeled vertices is given in A295193. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 08 2020

			T(8,3) = 6. Edge-lists for the 6 3-regular 8-node graphs:
  Graph 1: 12, 13, 14, 23, 24, 34, 56, 57, 58, 67, 68, 78
  Graph 2: 12, 13, 14, 24, 34, 26, 37, 56, 57, 58, 68, 78
  Graph 3: 12, 13, 23, 14, 47, 25, 58, 36, 45, 67, 68, 78
  Graph 4: 12, 13, 23, 14, 25, 36, 47, 48, 57, 58, 67, 68
  Graph 5: 12, 13, 24, 34, 15, 26, 37, 48, 56, 57, 68, 78
  Graph 6: 12, 23, 34, 45, 56, 67, 78, 18, 15, 26, 37, 48.
Triangle starts
  1;
  1, 1;
  1, 0, 1;
  1, 1, 1,  1;
  1, 0, 1,  0,    1;
  1, 1, 2,  2,    1,    1;
  1, 0, 2,  0,    2,    0,    1;
  1, 1, 3,  6,    6,    3,    1,    1;
  1, 0, 4,  0,   16,    0,    4,    0,  1;
  1, 1, 5, 21,   60,   60,   21,    5,  1, 1;
  1, 0, 6,  0,  266,    0,  266,    0,  6, 0, 1;
  1, 1, 9, 94, 1547, 7849, 7849, 1547, 94, 9, 1, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24, first 16 rows from Jason Kimberley)
Jason Kimberley, Not necessarily connected regular graphs (with girth at least 3)
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g
Markus Meringer, Fast generation of regular graphs and construction of cages, J. Graph Theory 30 (2) (1999) 137-146. [_Jason Kimberley_, Nov 24 2009]
Markus Meringer, Fast Generation of Regular Graphs and Construction of Cages, Univ. Bayreuth, 1999
Markus Meringer, Tables of Regular Graphs
Eric Weisstein's World of Mathematics, Regular Graph.

Row sums give A005176.
Regular graphs of degree k: A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).
Cf. A059441, A068933, A068934, A295193.

T(n,r) = A068934(n,r) + A068933(n,r).

More terms and comments from David Wasserman, Feb 22 2002
More terms from Eric W. Weisstein, Oct 19 2002
Description corrected (changed 'orders' to 'degrees') by Jason Kimberley, Sep 06 2009
Extended to the sixteenth row (in the b-file) by Jason Kimberley, Sep 24 2009

A014378 Number of connected regular graphs of degree 8 with n nodes.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 6, 94, 10786, 3459386, 1470293676, 733351105935, 423187422492342, 281341168330848873, 214755319657939505395, 187549729101764460261498, 186685399408147545744203815, 210977245260028917322933154987

Offset: 0

N. J. A. Sloane

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

			a(0)=1 because the null graph (with no vertices) is vacuously 8-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, Connected Graph
Eric Weisstein's World of Mathematics, Octic Graph
Eric Weisstein's World of Mathematics, Regular Graph

Contribution (almost all) from Jason Kimberley, Feb 10 2011: (Start)
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)

a(n) = A184983(n) + A181154(n).
a(n) = A180260(n) + A165878(n).
This sequence is the inverse Euler transformation of A180260.

Using the symmetry of A051031, a(15) and a(16) were appended by Jason Kimberley, Sep 25 2009

a(17)-a(22) from Andrew Howroyd, Mar 13 2020

A165626 Number of 5-regular graphs (quintic graphs) on 2n vertices.

Original entry on oeis.org

1, 0, 0, 1, 3, 60, 7849, 3459386, 2585136741, 2807105258926, 4221456120848125, 8516994772686533749, 22470883220896245217626, 75883288448434648617038134, 322040154712674550886226182668

Offset: 0

Jason Kimberley, Sep 22 2009

Because the triangle A051031 is symmetric, a(n) is also the number of (2n-6)-regular graphs on 2n vertices.

Jason Kimberley, Index of sequences counting not necessarily 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.
N. J. A. Sloane, Transforms

5-regular simple graphs: A006821 (connected), A165655 (disconnected), this sequence (not necessarily connected).

Regular graphs A005176 (any degree), A051031 (triangular array), specified degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), this sequence (k=5), A165627 (k=6), A165628 (k=7), A180260 (k=8).

A006821 = Cases[Import["https://oeis.org/A006821/b006821.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A006821] (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

Euler transform of A006821.

Regular graphs cross-references edited by Jason Kimberley, Nov 07 2009
a(9) from Jason Kimberley, Nov 24 2009
a(10)-a(14) from Andrew Howroyd, Mar 10 2020

A165627 Number of 6-regular graphs (sextic graphs) on n vertices.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 1, 4, 21, 266, 7849, 367860, 21609301, 1470293676, 113314233813, 9799685588961, 945095823831333, 101114579937196179, 11945375659140003692, 1551593789610531820695, 220716215902794066709555, 34259321384370735003091907, 5782740798229835127025560294

Offset: 0

Jason Kimberley, Sep 22 2009

Because the triangle A051031 is symmetric, a(n) is also the number of (n-7)-regular graphs on n vertices.

Georg Grasegger, Hakan Guler, Bill Jackson, Anthony Nixon, Flexible circuits in the d-dimensional rigidity matroid, arXiv:2003.06648 [math.CO], 2020.
Jason Kimberley, Index of sequences counting not necessarily 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.
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Regular Graph
Eric Weisstein's World of Mathematics, Sextic Graph

6-regular simple graphs: A006822 (connected), A165656 (disconnected), this sequence (not necessarily connected).

Regular graphs A005176 (any degree), A051031 (triangular array), chosen degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), this sequence (k=6), A165628 (k=7), A180260 (k=8).

A006822 = Cases[Import["https://oeis.org/A006822/b006822.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A006822] (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

Euler transformation of A006822.

Cross-references edited by Jason Kimberley, Nov 07 2009 and Oct 17 2011
a(17) from Jason Kimberley, Dec 30 2010
a(18)-a(24) from Andrew Howroyd, Mar 07 2020

A165628 Number of 7-regular graphs (septic graphs) on 2n vertices.

Original entry on oeis.org

1, 0, 0, 0, 1, 5, 1547, 21609301, 733351105935, 42700033549946255, 4073194598236125134140, 613969628444792223023625238, 141515621596238755267618266465449

Offset: 0

Jason Kimberley, Sep 22 2009

Because the triangle A051031 is symmetric, a(n) is also the number of (2n-8)-regular graphs on 2n vertices.

Jason Kimberley, Index of sequences counting not necessarily 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.
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Septic Graph

7-regular simple graphs: A014377 (connected), A165877 (disconnected), this sequence (not necessarily connected).

Regular graphs A005176 (any degree), A051031 (triangular array), chosen degrees: A000012 (k=0), A059841 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), this sequence (k=7), A180260 (k=8).

A014377 = Cases[Import["https://oeis.org/A014377/b014377.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A014377] (* Jean-François Alcover, Dec 04 2019, updated Mar 18 2020 *)

Euler transformation of A014377.

Cross-references edited by Jason Kimberley, Nov 07 2009 and Oct 17 2011
a(9)-a(11) from Andrew Howroyd, Mar 09 2020
a(12) from Andrew Howroyd, May 19 2020

A165878 Number of disconnected 8-regular simple graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 7, 100, 10901, 3470736, 1473822243, 734843169811, 423929978716908, 281768931380519766, 215039290728074333738, 187766225244288486398132, 186874272297562916477691894, 211165081721567703008217979077

Offset: 0

Jason Kimberley, Sep 29 2009

			The a(18)=1 graph is K_9+K_9.

Jason Kimberley, Disconnected regular graphs (with girth at least 3)
Jason Kimberley, Index of sequences counting disconnected k-regular simple graphs with girth at least g
Eric Weisstein's World of Mathematics, Disconnected Graph
Eric Weisstein's World of Mathematics, Octic Graph

8-regular simple graphs: A014378 (connected), this sequence (disconnected), A180260 (not necessarily connected).

Disconnected regular simple graphs: A068932 (any degree), A068933 (triangular array), specified degree k: A165652 (k=2), A165653 (k=3), A033483 (k=4), A165655 (k=5), A165656 (k=6), A165877 (k=7), this sequence (k=8), A185293 (k=9), A185203 (k=10), A185213 (k=11).

a = A180260 - A014378 = Euler_transformation(A014378) - A014378.

a(n) = D(n, 8) in the triangle A068933.

Terms a(26) and beyond from Andrew Howroyd, May 20 2020

cp's OEIS Frontend

A005176 Number of regular graphs with n unlabeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions

A005638 Number of unlabeled trivalent (or cubic) graphs with 2n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A051031 Triangle read by rows: T(n,r) is the number of not necessarily connected r-regular graphs with n nodes, 0 <= r < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A014378 Number of connected regular graphs of degree 8 with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A165626 Number of 5-regular graphs (quintic graphs) on 2n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165627 Number of 6-regular graphs (sextic graphs) on n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165628 Number of 7-regular graphs (septic graphs) on 2n vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165878 Number of disconnected 8-regular simple graphs on n vertices.

Views

Author

Keywords

Examples

Links