A005638 -id:A005638 - cp's OEIS frontend

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

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

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

A185335 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth at least 5.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 2, 9, 49, 455, 5784, 90940, 1620491, 31478651, 656784488, 14621878339, 345975756388

Offset: 0

Jason Kimberley, Jan 28 2011

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

3-regular simple graphs with girth at least 5: A014372 (connected), A185235 (disconnected), this sequence (not necessarily connected).
Not necessarily connected 3-regular simple graphs with girth *at least* g: A005638 (g=3), A185334 (g=4), this sequence (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).
Not necessarily connected k-regular simple graphs with girth at least 5: A185315 (any k), A185305 (triangle); specified degree k: A185325 (k=2), this sequence (k=3).

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

This sequence is the Euler transformation of A014372.

A180260 Number of not necessarily connected 8-regular simple graphs on n vertices.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 6, 94, 10786, 3459386, 1470293676, 733351105935, 423187422492342, 281341168330848874, 214755319657939505396, 187549729101764460261505, 186685399408147545744203915, 210977245260028917322933165888

Offset: 0

Jason Kimberley, Jan 17 2011

The Euler transformation currently does nothing: for n < 18, a(n) = A014378(n).

			The a(0)=1 graph is K_0 (vacuously 8-regular).
The a(9)=1 graph is K_9.

Eric Weisstein's World of Mathematics, Octic Graph

8-regular simple graphs: A014378 (connected), A165878 (disconnected), this sequence (not necessarily connected).
Not necessarily connected regular simple graphs: A005176 (any degree), A051031 (triangular array), specified degree k: A000012 (k=0), A000012 (k=1), A008483 (k=2), A005638 (k=3), A033301 (k=4), A165626 (k=5), A165627 (k=6), A165628 (k=7), this sequence (k=8).
8-regular not necessarily connected graphs: this sequence (simple graphs), A129437 (multigraphs with loops allowed), A129426 (multigraphs with loops forbidden).

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

Euler transformation of A014378.

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

A032355 Number of connected transitive trivalent (or cubic) graphs with 2n nodes.

Original entry on oeis.org

1, 2, 2, 3, 4, 3, 4, 5, 7, 3, 11, 5, 6, 10, 10, 5, 12, 5, 12, 10, 7, 5, 32, 9, 10, 13, 16, 7, 38, 7, 26, 11, 12, 11, 37, 9, 11, 14, 33, 9, 30, 9, 17, 21, 13, 9, 90, 13, 25, 16, 22, 11, 42, 19, 38, 18, 18, 11, 105, 13, 17, 26, 83, 19, 35, 13, 28, 19, 35, 13, 124, 15, 22, 28, 27, 19, 46, 15, 104, 43, 24, 15, 99, 23, 23, 23, 45, 17, 80, 25, 31, 26, 25, 23, 274, 19, 35, 31, 61, 19

Offset: 2

Ronald C. Read

Read and Wilson give counts of connected transitive graphs. Gordon Royle states that there are 17 transitive 32-node graphs. Read and Wilson state that 10 of them are connected. - Richard Sabey, Oct 11 2012

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

N. J. A. Sloane, Table of n, a(n) for n = 2..640, taken from the work of Primož Potočnik, Pablo Spiga and Gabriel Verret.
Primož Potočnik, Pablo Spiga and Gabriel Verret, A census of small connected cubic vertex-transitive graphs
Gordon Royle, There are 677402 vertex-transitive graphs on 32 vertices
Gordon Royle, Cubic transitive graphs [Broken link]
Eric Weisstein's World of Mathematics, Cubic Vertex-Transitive Graph

Cf. A005638, A002851, A241167 (Euler transf.).

"Connected" added by Richard Sabey, Oct 11 2012
Link provided that, in principle, gives values up to n=640. Extended to n=30 from that link by Allan C. Wechsler, Apr 18 2014
Extended to 640 from same source by N. J. A. Sloane, Apr 19 2014

A361361 Triangle read by rows: T(n,k) is the number of bicolored cubic graphs on 2n unlabeled vertices with k vertices of the first color, n >= 0, 0 <= k <= 2*n.

Original entry on oeis.org

1, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 5, 5, 5, 2, 2, 6, 11, 33, 48, 66, 48, 33, 11, 6, 21, 68, 257, 556, 950, 1071, 950, 556, 257, 68, 21, 94, 510, 2443, 7126, 15393, 23644, 27606, 23644, 15393, 7126, 2443, 510, 94, 540, 4712, 27682, 102122, 270957, 526783, 781292, 887305, 781292, 526783, 270957, 102122, 27682, 4712, 540

Offset: 0

Andrew Howroyd, Mar 10 2023

Adjacent vertices may have the same color.

			Triangle begins:
  1
  0,   0,  0;
  1,   1,  1,    1,   1;
  2,   2,  5,    5,   5,    2,   2;
  6,  11, 33,   48,  66,   48,  33,  11,   6;
  21, 68, 257, 556, 950, 1071, 950, 556, 257, 68, 21;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..440 (rows 0..20)

Columns k=0..2 are A005638, A361410, A361411.
Row sums are A361362.
Central coefficients are A361409.
Cf. A321304 (connected), A361404.

A006712 Number of 3-edge-colored trivalent graphs with 2n labeled nodes.

Original entry on oeis.org

6, 480, 197820, 150474240, 208857587400, 471804812519040, 1625459273858019600, 8112729590064978278400, 56342429224416522460072800, 527075322501595757416502976000, 6466573585901882433727764077860800, 101749747195531624711768653503416320000

Offset: 2

N. J. A. Sloane

nonn

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 2..50
Sean A. Irvine, Illustration of initial terms
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)

Cf. A006713 (for connected cases), A248361 (for the incorrect values). See also A002830, A002831, A005638.

dpermcount(v) = {my(m=1,s=0,k=0,t); for(i=1,#v,t=v[i]; k=if(i>1&&t==v[i-1],k+1,1); m*=2*t*k;s+=2*t); s!/m}
S(n,x)={vector(n, n, if(n>1, sum(k=0, n, binomial(2*n-k,k)*2*n/(2*n-k)*x^k), 0))}
q(n,s)={my(t=0); if(n>1, forpart(p=n, t+=dpermcount(p)*prod(i=1, #p, s[p[i]]), [2,n])); t}
a(n)={my(p=q(n,S(n,x))); sum(i=0, poldegree(p), polcoeff(p,n-i)*(-1)^(n-i)*(2*i)!/(2^i*i!))} \\ Andrew Howroyd, Dec 18 2017

a(5)-a(6) corrected and a(7)-a(10) from Sean A. Irvine, Oct 05 2014

Terms a(11) and beyond from Andrew Howroyd, Dec 18 2017

A361407 Number of connected cubic graphs on 2n unlabeled vertices rooted at a vertex.

Original entry on oeis.org

0, 1, 2, 10, 64, 490, 4595, 51063, 657623, 9592204, 155630924, 2771922417, 53673859357, 1121581872170, 25143397213226, 601751140758134, 15310778492310274, 412656423154230159, 11743600063060974656, 351882591907696156959

Offset: 1

Andrew Howroyd, Mar 11 2023

nonn

Column k=1 of A321304.

Cf. A002851, A005638, A361408, A361410.

G.f.: B(x)/C(x) where B(x) is the g.f. of A361410 and C(x) is the g.f. of A005638.

A059282 Number of symmetric trivalent (or cubic) connected graphs on 2n nodes (the Foster census).

Original entry on oeis.org

0, 1, 1, 1, 1, 0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 3, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 2, 2, 0, 1, 1, 0, 1, 1, 3, 1, 0, 0, 2, 1, 0, 1, 2, 0, 0, 1, 0, 0, 0, 0, 2, 1, 0, 1, 1, 0, 0, 1, 0, 3, 0, 0, 6, 0, 0, 0, 0, 0, 0, 4, 0, 1, 0, 0, 3, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 3, 1, 3, 1, 3, 0, 0, 0, 0, 2, 0, 0, 3, 1, 0, 0, 1, 1, 0, 1, 4, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 0, 0, 2, 1, 0, 0, 1

Offset: 1

N. J. A. Sloane, Jan 24 2001

Potočnik et al. refer to these as arc-transitive connected cubic vertex-transitive graphs.

Marston Conder (Email to N. J. A. Sloane, May 08 2017) remarks that "the first 5000 terms of A091430 are the same as the first 5000 terms of this sequence, with the exception of the 5th and 14th terms (corresponding to the Petersen graph and the Coxeter graph). I verified this soon after completing the determination of all connected symmetric 3-valent graphs of order up to 10000, in June 2011."

			The first example is K_4 with 4 nodes, thus a(2) = 1.

I. Z. Bouwer, W. W. Chernoff, B. Monson and Z. Star, The Foster Census (Charles Babbage Research Centre, 1988), ISBN 0-919611-19-2.

Marston Conder, Table of n, a(n) for n = 1..5000 [The first 640 terms were added by N. J. A. Sloane, based on the work of Primož Potočnik, Pablo Spiga and Gabriel Verret]
Marston Conder, Home Page (Contains tables of regular maps, hypermaps and polytopes, trivalent symmetric graphs, and surface actions)
Marston Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices
Marston Conder and P. Dobcsányi, Trivalent symmetric graphs on up to 768 vertices, J. Combinatorial Mathematics & Combinatorial Computing 40 (2002), 41-63.
Primož Potočnik, Pablo Spiga and Gabriel Verret, A census of small connected cubic vertex-transitive graphs (See the sub-page Table.html) [Broken link]
Gordon Royle et al., Cubic symmetric graphs (The Foster Census) [Broken link]
Gordon Royle, Cubic transitive graphs
Eric Weisstein's World of Mathematics, Cubic Symmetric Graph

Cf. A005638, A002851, A032355, A091430.

Updated all links. Corrected entries based on the Potočnik et al. table. - N. J. A. Sloane, Apr 19 2014

A185130 Irregular triangle E(n,g) counting not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g.

Original entry on oeis.org

1, 1, 1, 4, 2, 15, 5, 1, 71, 21, 2, 428, 103, 8, 1, 3406, 752, 48, 1, 34270, 7385, 450, 5, 418621, 91939, 5752, 32, 5937051, 1345933, 90555, 385, 94782437, 22170664, 1612917, 7573, 1, 1670327647, 401399440, 31297424, 181224, 3, 32090011476, 7887389438

Offset: 2

Jason Kimberley, Dec 26 2012

The first column is for girth exactly 3. The column for girth exactly g begins when 2n reaches A000066(g).

			1;
1, 1;
4, 2;
15, 5, 1;
71, 21, 2;
428, 103, 8, 1;
3406, 752, 48, 1;
34270, 7385, 450, 5;
418621, 91939, 5752, 32;
5937051, 1345933, 90555, 385;
94782437, 22170664, 1612917, 7573, 1;
1670327647, 401399440, 31297424, 181224, 3;
32090011476, 7887389438, 652159986, 4624481, 21;
666351752261, 166897766824, 14499787794, 122089999, 545, 1;
14859579573845, 3781593764772, 342646826428, 3328899592, 30368, 0;

Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g

Initial columns of this triangle: A185133 (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).

The n-th row is the sequence of differences of the n-th row of A185330:
E(n,g) = A185330(n,g) - A185330(n,g+1), once we have appended 0 to each row of A185330.
Hence the sum of the n-th row is A185330(n,3) = A005638(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A185335 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth at least 5.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A180260 Number of not necessarily connected 8-regular simple graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A032355 Number of connected transitive trivalent (or cubic) graphs with 2n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A361361 Triangle read by rows: T(n,k) is the number of bicolored cubic graphs on 2n unlabeled vertices with k vertices of the first color, n >= 0, 0 <= k <= 2*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A006712 Number of 3-edge-colored trivalent graphs with 2n labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Extensions

A361407 Number of connected cubic graphs on 2n unlabeled vertices rooted at a vertex.

Views

Author

Keywords

Crossrefs

Formula

A059282 Number of symmetric trivalent (or cubic) connected graphs on 2n nodes (the Foster census).

Views

Author

Keywords

Comments