A185335 -id:A185335 - cp's OEIS frontend

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

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

A185325 Number of partitions of n into parts >= 5.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 10, 13, 15, 18, 21, 26, 30, 36, 42, 50, 58, 70, 80, 95, 110, 129, 150, 176, 202, 236, 272, 317, 364, 423, 484, 560, 643, 740, 847, 975, 1112, 1277, 1456, 1666, 1897, 2168, 2464, 2809, 3189, 3627, 4112, 4673

Offset: 0

Jason Kimberley, Nov 11 2011

a(n) is also the number of not necessarily connected 2-regular graphs on n-vertices with girth at least 5 (all such graphs are simple). The integer i corresponds to the i-cycle; addition of integers corresponds to disconnected union of cycles.
By removing a single part of size 5, an A026798 partition of n becomes an A185325 partition of n - 5. Hence this sequence is essentially the same as A026798.
a(n) = number of partitions of n+4 such that 4*(number of parts) is a part. - Clark Kimberling, Feb 27 2014

G. C. Greubel, Table of n, a(n) for n = 0..1000
Kevin Beanland and Hung Viet Chu, On Schreier-type Sets, Partitions, and Compositions, arXiv:2311.01926 [math.CO], 2023.
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

2-regular simple graphs with girth at least 5: A185115 (connected), A185225 (disconnected), this sequence (not necessarily connected).
Not necessarily connected 2-regular graphs with girth at least g [partitions into parts >= g]: A026807 (triangle); chosen g: A000041 (g=1 -- multigraphs with loops allowed), A002865 (g=2 -- multigraphs with loops forbidden), A008483 (g=3), A008484 (g=4), this sequence (g=5), A185326 (g=6), A185327 (g=7), A185328 (g=8), A185329 (g=9).
Not necessarily connected 2-regular graphs with girth exactly g [partitions with smallest part g]: A026794 (triangle); chosen g: A002865 (g=2), A026796 (g=3), A026797 (g=4), A026798 (g=5), A026799 (g=6), A026800(g=7), A026801 (g=8), A026802 (g=9), A026803 (g=10).
Not necessarily connected k-regular simple graphs with girth at least 5: A185315 (any k), A185305 (triangle); specified degree k: this sequence (k=2), A185335 (k=3).
Cf. A008484, A008483.

p :=  func< n | n lt 0 select 0 else NumberOfPartitions(n) >;
A185325 := func;
[A185325(n):n in[0..60]];

R:=PowerSeriesRing(Integers(), 70); Coefficients(R!( 1/(&*[1-x^(m+5): m in [0..80]]) )); // G. C. Greubel, Nov 03 2019

seq(coeff(series(1/mul(1-x^(m+5), m = 0..80), x, n+1), x, n), n = 0..70); # G. C. Greubel, Nov 03 2019

Drop[Table[Count[IntegerPartitions[n], p_ /; MemberQ[p, 4*Length[p]]], {n, 40}], 3]  (* Clark Kimberling, Feb 27 2014 *)
CoefficientList[Series[1/QPochhammer[x^5, x], {x, 0, 70}], x] (* G. C. Greubel, Nov 03 2019 *)

my(x='x+O('x^70)); Vec(1/prod(m=0,80, 1-x^(m+5))) \\ G. C. Greubel, Nov 03 2019

def A185325_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/product((1-x^(m+5)) for m in (0..80)) ).list()
A185325_list(70) # G. C. Greubel, Nov 03 2019

G.f.: Product_{m>=5} 1/(1-x^m).
Given by p(n) -p(n-1) -p(n-2) +2*p(n-5) -p(n-8) -p(n-9) +p(n-10), where p(n) = A000041(n). - Shanzhen Gao, Oct 28 2010 [sign of 10 corrected from + to -, and moved from A026798 to this sequence by Jason Kimberley].
This sequence is the Euler transformation of A185115.
a(n) ~ exp(Pi*sqrt(2*n/3)) * Pi^4 / (6*sqrt(3)*n^3). - Vaclav Kotesovec, Jun 02 2018
G.f.: exp(Sum_{k>=1} x^(5*k)/(k*(1 - x^k))). - Ilya Gutkovskiy, Aug 21 2018
G.f.: 1 + Sum_{n >= 1} x^(n+4)/Product_{k = 0..n-1} (1 - x^(k+5)). - Peter Bala, Dec 01 2024

A014372 Number of trivalent connected simple graphs with 2n nodes and girth at least 5.

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 2, 9, 49, 455, 5783, 90938, 1620479, 31478584, 656783890, 14621871204, 345975648562

Offset: 0

N. J. A. Sloane

The null graph on 0 vertices is vacuously connected and 3-regular; since it is acyclic, it has infinite girth. - Jason Kimberley, Jan 29 2011

Brendan McKay has observed that a(13) = 31478584 is output by genreg, minibaum, and snarkhunter, but Meringer's table currently has a(13) = 31478582. - Jason Kimberley, May 17 2017

CRC Handbook of Combinatorial Designs, 1996, p. 647.

G. Brinkmann, J. Goedgebeur and B. D. McKay, Generation of cubic graphs, Discr. Math. Theor. Comp. Sci. 13 (2) (2011) 69-80.
House of Graphs, Cubic graphs.
Jason Kimberley, Connected regular graphs with girth at least 5
Jason Kimberley, Index of sequences counting 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.

Contribution from Jason Kimberley, 2010, 2011, and 2012: (Start)
3-regular simple graphs with girth at least 5: this sequence (connected), A185235 (disconnected), A185335 (not necessarily connected).
Connected k-regular simple graphs with girth at least 5: A186725 (all k), A186715 (triangle); A185115 (k=2), this sequence (k=3), A058343 (k=4), A205295 (g=5).
Connected 3-regular simple graphs with girth at least g: A185131 (triangle); A002851 (g=3), A014371 (g=4), this sequence (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8).
Connected 3-regular simple graphs with girth exactly g: A198303 (triangle); A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7). (End)

Terms a(15) and a(16) appended, from running Meringer's GENREG for 28.7 and 715.2 processor days at U. Ncle., by Jason Kimberley, Jun 28 2010.

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

Original entry on oeis.org

1, 0, 0, 1, 2, 6, 23, 112, 801, 7840, 97723, 1436873, 23791155, 432878091, 8544173926, 181519645163, 4127569521160

Offset: 0

Jason Kimberley, Feb 15 2011

The null graph on 0 vertices is vacuously 3-regular; since it is acyclic, it has infinite girth.

Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 4
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 4: A014371 (connected), A185234 (disconnected), this sequence (not necessarily connected).
Not necessarily connected k-regular simple graphs with girth at least 4: A185314 (any k), A185304 (triangle); specified degree k: A008484 (k=2), this sequence (k=3), A185344 (k=4), A185354 (k=5), A185364 (k=6).
Not necessarily connected 3-regular simple graphs with girth *at least* g: A005638 (g=3), this sequence (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).

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

Euler transformation of A014371.

A185134 Number of, not necessarily connected, 3-regular simple graphs on 2n vertices with girth exactly 4.

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 21, 103, 752, 7385, 91939, 1345933, 22170664, 401399440, 7887389438, 166897766824, 3781593764772

Offset: 0

Jason Kimberley, Mar 21 2012

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

Not necessarily connected k-regular simple graphs girth exactly 4: A198314 (any k), A185644 (triangle); fixed k: A026797 (k=2), this sequence (k=3), A185144 (k=4).

Not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g: A185130 (triangle); fixed g: A185133 (g=3), this sequence (g=4), A185135 (g=5), A185136 (g=6).

a(n) = A185334(n) - A185335(n).

a(n) = A006924(n) + A185034(n).

A185315 Number of, not necessarily connected, regular simple graphs on n vertices with girth at least 5.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 2, 3, 2, 5, 3, 7, 4, 15, 6, 57, 8, 466, 12, 5801, 24, 91091, 3939, 1744378, 4132022, 163639295, 4018022192, 119026596500

Offset: 0

Jason Kimberley, Dec 12 2012

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

Not necessarily connected k-regular simple graphs with girth at least 5: this sequence (any k), A185305 (triangle); specified degree k: A185325 (k=2), A185335 (k=3).

Not necessarily connected regular simple graphs with girth at least g: A005176 (g=3), A185314 (g=4), this sequence (g=5), A185316 (g=6), A185317 (g=7), A185318 (g=8), A185319 (g=9).

a(n) = A186725(n) + A185215(n).

A185135 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly 5.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 8, 48, 450, 5752, 90555, 1612917, 31297424, 652159986, 14499787794, 342646826428

Offset: 0

Jason Kimberley, Mar 21 2012

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

Not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g: A185130 (triangle); fixed g: A185133 (g=3), A185134 (g=4), this sequence (g=5), A185136 (g=6).

a(n) = A185335(n) - A185336(n).

a(n) = A006925(n) + A185035(n).

A185305 Triangular array E(n,k) counting not necessarily connected k-regular simple graphs on n vertices with girth at least 5.

Original entry on oeis.org

1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 2, 0, 1, 1, 3, 2, 1, 0, 3, 0, 1, 1, 4, 9, 1, 0, 5, 0, 1, 1, 6, 49, 1, 0, 7, 0, 1, 1, 9, 455, 1, 0, 10, 0, 1, 1, 1, 13, 5784, 2, 1, 0, 15, 0, 8, 1, 1, 18, 90940, 131, 1, 0, 21, 0, 3917, 1, 1, 26, 1620491, 123859

Offset: 1

Jason Kimberley, Feb 21 2013

Row sums give A185315.

			01: 1;
02: 1, 1;
03: 1, 0;
04: 1, 1;
05: 1, 0, 1;
06: 1, 1, 1;
07: 1, 0, 1;
08: 1, 1, 1;
09: 1, 0, 1;
10: 1, 1, 2, 1;
11: 1, 0, 2, 0;
12: 1, 1, 3, 2;
13: 1, 0, 3, 0;
14: 1, 1, 4, 9;
15: 1, 0, 5, 0;
16: 1, 1, 6, 49;
17: 1, 0, 7, 0;
18: 1, 1, 9, 455;
19: 1, 0, 10, 0, 1;
20: 1, 1, 13, 5784, 2;
21: 1, 0, 15, 0, 8;
22: 1, 1, 18, 90940, 131;
23: 1, 0, 21, 0, 3917;
24: 1, 1, 26, 1620491, 123859;
25: 1, 0, 30, 0, 4131991;
26: 1, 1, 36, 31478649, 132160608;
27: 1, 0, 42, 0, 4018022149;
28: 1, 1, 50, 656784488, 118369811960;

Jason Kimberley, Table of n, a(i)=E(n,k) for i = 1..108 (n = 1..28)
Jason Kimberley, Not necessarily connected k-regular graphs with girth at least 5
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

Not necessarily connected k-regular simple graphs with girth at least 5: A185315 (any k), this sequence (triangle); specified degree k: A185325 (k=2), A185335 (k=3).

E(n,k) = A186715(n,k) + A185205(n,k).

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

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 1, 5, 32, 385, 7574, 181227, 4624502, 122090545, 3328929960, 93990692632, 2754222605808

Offset: 0

Jason Kimberley, Jan 28 2012

The null graph on 0 vertices is vacuously 3-regular; since it is acyclic, it has infinite girth.

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 6: A014374 (connected), A185236 (disconnected), this sequence (not necessarily connected).
Not necessarily connected k-regular simple graphs with girth at least 6: A185326 (k=2), this sequence (k=3).
Not necessarily connected 3-regular simple graphs with girth *at least* g: A005638 (g=3), A185334 (g=4), A185335 (g=5), this sequence (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).

A014374 = Cases[Import["https://oeis.org/A014374/b014374.txt", "Table"], {, }][[All, 2]];
etr[f_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d f[d], {d, Divisors[j]}] b[n - j], {j, 1, n}]/n]; b];
a = etr[A014374[[# + 1]]&];
a /@ Range[0, Length[A014374] - 1] (* Jean-François Alcover, Dec 04 2019 *)

Euler transformation of A014374.

a(18) from A014374 from Jean-François Alcover, Dec 04 2019

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A185325 Number of partitions of n into parts >= 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Maple

Mathematica

PARI

Sage

Formula

A014372 Number of trivalent connected simple graphs with 2n nodes and girth at least 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A185134 Number of, not necessarily connected, 3-regular simple graphs on 2n vertices with girth exactly 4.

Views

Author

Keywords

Links

Crossrefs

Formula

A185315 Number of, not necessarily connected, regular simple graphs on n vertices with girth at least 5.

Views

Author

Keywords

Links

Crossrefs

Formula

A185135 Number of not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly 5.

Views

Author

Keywords

Links

Crossrefs

Formula

A185305 Triangular array E(n,k) counting not necessarily connected k-regular simple graphs on n vertices with girth at least 5.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments