login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A051031 Triangle read by rows: T(n,r) is the number of not necessarily connected r-regular graphs with n nodes, 0 <= r < n. 21
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,18

COMMENTS

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

LINKS

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

FORMULA

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

EXAMPLE

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;

  ...

CROSSREFS

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, A295193.

Sequence in context: A319372 A319367 A234514 * A181059 A111915 A066520

Adjacent sequences:  A051028 A051029 A051030 * A051032 A051033 A051034

KEYWORD

nonn,tabl

AUTHOR

Eric W. Weisstein

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 29 17:53 EST 2020. Contains 338769 sequences. (Running on oeis4.)