A068933 -id:A068933 - cp's OEIS frontend

A068934 Triangular array C(n, r) = number of connected r-regular graphs with n nodes, 0 <= r < n.

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

Offset: 1

David Wasserman, Mar 08 2002

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

			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;

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.

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

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

Edited by Jason Kimberley, Sep 23 2009, Nov 2011, Jan 2012, and Mar 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

A165652 Number of disconnected 2-regular graphs on n vertices.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 2, 3, 4, 5, 8, 9, 12, 16, 20, 24, 32, 38, 48, 59, 72, 87, 109, 129, 157, 190, 229, 272, 330, 390, 467, 555, 659, 778, 926, 1086, 1283, 1509, 1774, 2074, 2437, 2841, 3322, 3871, 4509, 5236, 6094, 7055, 8181, 9464, 10944, 12624, 14577, 16778, 19322, 22209

Offset: 0

Jason Kimberley, Sep 28 2009

a(n) is also the number of partitions of n such that each part i satisfies 2

For n>=2, it appears that a(n+1) is the number of (1,0)-separable partitions of n, as defined at A239482. For example, the four (1,0)-separable partitions of 9 are 621, 531, 441, 31212, corresponding to a(10) = 4. - Clark Kimberling, Mar 21 2014.

			The a(6)=1 graph is C_3+C_3. The a(7)=1 graph is C_3+C_4. The a(8)=2 graphs are C_3+C_5, C_4+C_4. The a(9)=3 graphs are 3C_3, C_3+C_6, C_4+C_5.

Andrew van den Hoeven, Table of n, a(n) for n = 0..10000
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

2-regular simple graphs: A179184 (connected), this sequence (disconnected), A008483 (not necessarily connected).
Disconnected regular simple graphs: A068932 (any degree), A068933 (triangular array), specified degree k: A157928 (k=0), A157928 (k=1), this sequence (k=2), A165653 (k=3), A033483 (k=4), A165655 (k=5), A165656 (k=6), A165877 (k=7), A165878 (k=8).
Disconnected 2-regular simple graphs with girth at least g: this sequence (g=3), A185224 (g=4), A185225 (g=5), A185226 (g=6), A185227 (g=7), A185228 (g=8), A185229 (g=9).
Cf. A239482.

p := NumberOfPartitions; a := func< n | n lt 3 select 0 else p(n) - p(n-1) - p(n-2) + p(n-3) - 1 >;

a = A008483 - A179184 = Euler_tranformation(A179184) - A179184.
For n > 2, since there is exactly one connected 2-regular graph on n vertices (the n cycle C_n) then a(n) = A008483(n) - 1.
(A008483(n) is also the number of not necessarily connected 2-regular graphs on n vertices.)
Column D(n, 2) in the triangle A068933.

A068932 Number of disconnected regular graphs with n nodes.

Original entry on oeis.org

0, 0, 1, 1, 2, 1, 3, 2, 5, 4, 9, 7, 23, 18, 74, 106, 619, 2076, 22526, 112834, 4799825, 31138965, 4207943011, 115979718015, 13482672647959

Offset: 0

David Wasserman, Mar 08 2002

A graph is called regular if every node has the same number of edges.

Row sums of A068933.

Cf. A005176, A005177, A068933.

a(n) = A005176(n) - A005177(n).

a(22) corrected and a(23) appended Sep 28 2009, a(24) appended Nov 24 2009, by Jason Kimberley.

a(0)=0 (due to the empty graph being vacuously connected) inserted by Jason Kimberley, Apr 11 2012

A033483 Number of disconnected 4-valent (or quartic) graphs with n nodes.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 3, 8, 25, 88, 378, 2026, 13351, 104595, 930586, 9124662, 96699987, 1095469608, 13175272208, 167460699184, 2241578965849, 31510542635443, 464047929509794, 7143991172244290, 114749135506381940, 1919658575933845129, 33393712487076999918, 603152722419661386031

Offset: 0

Ronald C. Read

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

Jason Kimberley, Index of sequences counting disconnected k-regular simple graphs with girth at least g
N. J. A. Sloane, Transforms
Eric Weisstein's World of Mathematics, Disconnected Graph
Eric Weisstein's World of Mathematics, Quartic Graph

4-regular simple graphs: A006820 (connected), this sequence (disconnected), A033301 (not necessarily connected). - Jason Kimberley, Jan 08 2011
Disconnected regular simple graphs: A068932 (any degree), A068933 (triangular array), specified degree k: A165652 (k=2), A165653 (k=3), this sequence (k=4), A165655 (k=5), A165656 (k=6), A165877 (k=7), A165878 (k=8), A185293 (k=9), A185203 (k=10), A185213 (k=11).
Disconnected 4-regular simple graphs with girth at least g: this sequence (g=3), A185244 (g=4), A185245 (g=5), A185246 (g=6).

A006820 = Cases[Import["https://oeis.org/A006820/b006820.txt", "Table"], {, }][[All, 2]];
(* EulerTransform is defined in A005195 *)
EulerTransform[Rest @ A006820] - A006820 (* Jean-François Alcover, Jan 21 2020, updated Mar 17 2020 *)

a(n) = A033301(n) - A006820(n) = Euler_transformation(A006820) - A006820.

a(n) = A068933(n, 4). - Jason Kimberley, Sep 27 2009 and Jan 08 2011

Terms a(16)-a(18) from Martin Fuller, Dec 04 2006
Terms a(19)-a(26) from Jason Kimberley, Sep 27 2009 and Dec 30 2010
Terms a(27)-a(33), due to the extension of A006820 by Andrew Howroyd, from Jason Kimberley, Mar 12 2020

A165653 Number of disconnected 3-regular (cubic) graphs on 2n vertices.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 9, 31, 147, 809, 5855, 54477, 633057, 8724874, 137047391, 2391169355, 45626910415, 942659626031, 20937539944549, 497209670658529, 12566853576025106, 336749273734805530, 9534909974420181226

Offset: 0

Jason Kimberley, Sep 28 2009

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, Cubic Graph
Eric Weisstein's World of Mathematics, Disconnected Graph

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

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

A[s_Integer] := With[{s6 = StringPadLeft[ToString[s], 6, "0"]}, Cases[ Import["https://oeis.org/A" <> s6 <> "/b" <> s6 <> ".txt", "Table"], {, }][[All, 2]]];
A005638 = A@005638;
A002851 = A@002851;
a[n_] := A005638[[n + 1]] - A002851[[n + 1]];
a /@ Range[0, 20] (* Jean-François Alcover, Jan 21 2020 *)

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

a(n) = A068933(2n, 3).

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 3, 66, 8029, 3484760, 2595985770, 2815099031417, 4230059694039460, 8529853839173455678, 22496718465713456081402, 75951258300080722467845995, 322269241532759484921710401976

Offset: 0

Jason Kimberley, Sep 28 2009

N. J. A. Sloane, Transforms
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, Quintic Graph

5-regular simple graphs: A006821 (connected), this sequence (disconnected), A165626 (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), this sequence (k=5), A165656 (k=6), A165877 (k=7), A165878 (k=8), A185293 (k=9), A185203 (k=10), A185213 (k=11).

a = A165626 - A006821 = Euler_transformation(A006821) - A006821.

a(n)=A068933(2n,5).

Terms a(13)-a(17), due to the extension of A006821 by Andrew Howroyd, from Jason Kimberley, Mar 12 2020

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 5, 25, 297, 8199, 377004, 22014143, 1493574756, 114880777582, 9919463450855, 955388277929620, 102101882472479938, 12050526046888229845, 1563967741064673811531, 222318116370232302781485, 34486536277291555593662301, 5817920265098158804699762770

Offset: 0

Jason Kimberley, Sep 28 2009

N. J. A. Sloane, Transforms
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, Regular Graph
Eric Weisstein's World of Mathematics, Sextic Graph

6-regular simple graphs: A006822 (connected), this sequence (disconnected), A165627 (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), this sequence (k=6), A165877 (k=7), A165878 (k=8), A185293 (k=9), A185203 (k=10), A185213 (k=11).

a = A165627 - A006822 = Euler_transformation(A006822) - A006822.

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

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

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

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 1, 5, 1562, 21617036, 733460349818, 42703733735064572, 4073409466378991404239, 613990076321940092226829047, 141518698937232822678583027258225

Offset: 0

Jason Kimberley, Sep 28 2009

N. J. A. Sloane, Transforms
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, Septic Graph

7-regular simple graphs: A014377 (connected), this sequence(disconnected), A165628 (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), this sequence (k=7), A165878 (k=8), A185293 (k=9), A185203 (k=10), A185213 (k=11).

a = A165628 - A014377 = Euler_transformation(A014377) - A014377.

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

a(13)-a(16) from Andrew Howroyd, May 20 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

Showing 1-10 of 17 results. Next

cp's OEIS Frontend

A068934 Triangular array C(n, r) = number of connected r-regular graphs with n nodes, 0 <= r < n.

Views

Author

Keywords

Comments

Examples

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

A165652 Number of disconnected 2-regular graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Formula

A068932 Number of disconnected regular graphs with n nodes.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A033483 Number of disconnected 4-valent (or quartic) graphs with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A165653 Number of disconnected 3-regular (cubic) graphs on 2n vertices.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

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

Views

Author

Keywords