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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A068934 Triangular array C(n, r) = number of connected r-regular graphs with n nodes, 0 <= r < n. 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,19

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

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24, first 16 rows from Jason Kimberley)

Jason Kimberley, Connected regular graphs (with girth at least 3)

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

Zhipeng Xu, Xiaolong Huang, Fabian Jimenez, Yuefan Deng, A new record of enumeration of regular graphs by parallel processing, arXiv:1907.12455 [cs.DM], 2019.

FORMULA

C(n, r) = A051031(n, r) - A068933(n, r).

Column k is the inverse Euler transform of column k of A051031. - Andrew Howroyd, Mar 10 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).

Sequence in context: A081227 A301469 A004610 * A035200 A198066 A141664

Adjacent sequences:  A068931 A068932 A068933 * A068935 A068936 A068937

KEYWORD

nonn,tabl,hard

AUTHOR

David Wasserman, Mar 08 2002

EXTENSIONS

Edited by Jason Kimberley, Sep 23 2009, Nov 2011, Jan 2012, and Mar 2012

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 April 16 04:49 EDT 2021. Contains 343030 sequences. (Running on oeis4.)