A324163 -id:A324163 - cp's OEIS frontend

A059441 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) giving number of regular labeled graphs with n nodes and degree k, read by rows.

1, 1, 1, 1, 0, 1, 1, 3, 3, 1, 1, 0, 12, 0, 1, 1, 15, 70, 70, 15, 1, 1, 0, 465, 0, 465, 0, 1, 1, 105, 3507, 19355, 19355, 3507, 105, 1, 1, 0, 30016, 0, 1024380, 0, 30016, 0, 1, 1, 945, 286884, 11180820, 66462606, 66462606, 11180820, 286884, 945, 1

Offset: 1

N. J. A. Sloane, Feb 01 2001

			1;
1,   1;
1,   0,       1;
1,   3,       3,        1;
1,   0,      12,        0,          1;
1,  15,      70,       70,         15,    1;
1,   0,     465,        0,        465,    0,   1;
1, 105,    3507,    19355,      19355, 3507, 105, 1;
1,   0,   30016,        0,    1024380, ...;
1, 945,  286884, 11180820,   66462606, ...;
1,   0, 3026655,        0, 5188453830, ...;

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 279.

Andrew Howroyd, Table of n, a(n) for n = 1..300 (rows 1..24)
Denis S. Krotov, [[2,10],[6,6]]-equitable partitions of the 12-cube, arXiv:2012.00038 [math.CO], 2020.
Brendan D. McKay, Applications of a technique for labeled enumeration, Congress. Numerantium, 40 (1983), 207-221. See page 216.
Wikipedia, Regular graph

Row sums are A295193.
Columns: A123023 (k=1), A001205 (k=2), A002829 (k=3, with alternating zeros), A005815 (k=4), A338978 (k=5, with alternating zeros), A339847 (k=6).
Cf. A051031 (unlabeled case), A324163 (connected case), A333351 (multigraphs).
Cf. A001147, A058891, A319189, A319190, A319612, A319729, A322635, A322659, A322698, A322704.

Table[SeriesCoefficient[Product[1+Times@@x/@s,{s,Subsets[Range[n],{2}]}],Sequence@@Table[{x[i],0,k},{i,n}]],{n,9},{k,0,n-1}] (* Gus Wiseman, Dec 24 2018 *)

for(n=1, 10, print(A059441(n))) \\ See A295193 for script, Andrew Howroyd, Aug 28 2019

a(37)-a(55) from Andrew Howroyd, Aug 25 2017

A004109 Number of connected trivalent (or cubic) labeled graphs with 2n nodes.

Original entry on oeis.org

1, 0, 1, 70, 19320, 11166120, 11543439600, 19491385914000, 50233275604512000, 187663723374359232000, 975937986889287117696000, 6838461558851342749449120000, 62856853767402275979616458240000, 741099150663748252073618880960000000, 10997077750618335243742188527076864000000

Offset: 0

N. J. A. Sloane

			From _R. J. Mathar_, Oct 18 2018: (Start)
For n=3, 2*n=6, the A002851(n)=2 graphs have multiplicities of 10 and 60 (sum 70).
For n=4, 2*n=8, the A002851(n)=5 graphs have multiplicities of 3360, 840, 2520, 10080 and 2520, (sum 19320). (The orders of the five Aut-groups are 8!/3360 =12, 8!/840=48, 8!/2520 =16, 8!/10080=4 and 8!/2520=16, i.e., all larger than 1 as indicated in A204328). (End)

R. C. Read, Some Enumeration Problems in Graph Theory. Ph.D. Dissertation, Department of Mathematics, Univ. London, 1958.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
R. W. Robinson, Computer print-out, no date. Gives first 29 terms.
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 = 0..100 (terms 1..29 from R. W. Robinson)
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 13.
R. C. Read, Letter to N. J. A. Sloane, Feb 04 1971 (gives initial terms of this sequence)
R. W. Robinson, Cubic labeled graphs, computer print-out, n.d.

See A002829 for not-necessarily-connected graphs, A002851 for connected unlabeled cases.

Cf. A324163.

Conjecture: a(n) ~ 2^(n + 1/2) * 3^n * n^(3*n) / exp(3*n+2). - Vaclav Kotesovec, Feb 17 2024

a(0)=1 prepended by Andrew Howroyd, Sep 02 2019

A322659 Number of connected regular simple graphs on n labeled vertices.

Original entry on oeis.org

1, 1, 1, 4, 13, 146, 826, 44808, 1074557, 155741296, 10381741786, 6939251270348, 2203360264480750, 4186526735251514044, 3747344007864300197810, 35041787059621536192399824, 156277111373298355107598128061, 4142122641757597729416733678931968

Offset: 1

Gus Wiseman, Dec 22 2018

nonn

A graph is regular if all vertices have the same degree.

Gus Wiseman, The a(5) = 13 connected regular simple graphs.
Gus Wiseman, The a(6) = 146 connected regular simple graphs.

Row sums of A324163.

Cf. A054921, A059441, A062740, A295193, A299353, A305078, A319190, A319612, A319729, A322635.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[If[n==1,1,Length[Select[Subsets[Subsets[Range[n],{2}]],And[Union@@#==Range[n],SameQ@@Length/@Split[Sort[Join@@#]],Length[csm[#]]==1]&]]],{n,6}]

a(8)-a(15) from Andrew Howroyd, Dec 23 2018

a(16)-a(18) from Andrew Howroyd, Sep 02 2019

A272905 Number of connected 4-regular (or quartic) labeled graphs with n nodes.

Original entry on oeis.org

0, 0, 0, 0, 1, 15, 465, 19355, 1024380, 66462480, 5188446900, 480413448900, 52113339432000, 6551243302804200, 945313572845842200, 155243683741953807000, 28797215441570535960000, 5993001571565164940784000, 1390759438984816084192008000

Offset: 1

Catherine Greenhill, May 09 2016

nonn

The e.g.f. for this sequence is the logarithm of the e.g.f. for the sequence of all 4-regular labeled graphs on n nodes (see A005815), using Wilf's exponential formula.

			The triangle of 4-valend labeled graphs with n>=1 nodes and 1<=k<=n components (row sums A005815) starts:
  0;
  0,0;
  0,0,0;
  0,0,0,0;
  1,0,0,0,0;
  15,0,0,0,0,0;
  465,0,0,0,0,0,0;
  19355,0,0,0,0,0,0,0;
  1024380,0,0,0,0,0,0,0,0;
  66462480,126,0,0,0,0,0,0,0,0;
  5188446900,6930,0,0,0,0,0,0,0,0,0;
  480413448900,472230,0,0,0,0,0,0,0,0,0,0;
  52113339432000,36878985,0,0,0,0,0,0,0,0,0,0,0;
  6551243302804200,3293696835,0,0,0,0,0,0,0,0,0,0,0,0;
  945313572845842200,334407638565,126126,0,0,0,0,0,0,0,0,0,0,0,0;
  155243683741953807000,38506555125675,15135120,0,0,0,0,0,0,0,0,0,0,0,0,0; - _R. J. Mathar_, Apr 29 2019

H. S. Wilf, generatingfunctionology (2nd edn.), Academic Press, 1994, Corollary 3.4.1, page 81.

Catherine Greenhill, Table of n, a(n) for n = 1..100
Élie de Panafieu, Asymptotic expansion of regular and connected regular graphs, arXiv:2408.12459 [math.CO], 2024. See p. 13.

Column k=4 of A324163.

See A005815 for not-necessarily-connected labeled 4-regular graphs.

egf := log((1+x-(1/3)*x^2-(1/6)*x^3)^(-1/2)*hypergeom([1/4, 3/4], [], -12*x*(x+2)*(x-1)/(x^3+2*x^2-6*x-6)^2)*exp(-x*(x^2-6)/(8*x+16)));
ser := convert(series(egf, x=0, 40), polynom):
seq(coeff(ser, x, i)*i!, i=0..degree(ser));

g[x_] := Log[(Exp[x*(6-x^2)/8/(2+x)]* HypergeometricPFQ[{1/4, 3/4}, {}, ((12 (1-x) * x *(2 + x))/(x^3 + 2*x^2 - 6*x - 6)^2)])/ Sqrt[1 + x - x^2/3 - x^3/6]]; Rest[ CoefficientList[ Series[g[x], {x, 0, 30}], x]* Range[0, 30]!] (* Giovanni Resta, May 09 2016 *)

E.g.f.: log((1+x-(1/3)*x^2-(1/6)*x^3)^(-1/2)*hypergeom([1/4, 3/4],[],-12*x*(x+2)*(x-1)/(x^3+2*x^2-6*x-6)^2)*exp(-x*(x^2-6)/(8*x+16))).

cp's OEIS Frontend

A059441 Triangle T(n,k) (n >= 1, 0 <= k <= n-1) giving number of regular labeled graphs with n nodes and degree k, read by rows.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A004109 Number of connected trivalent (or cubic) labeled graphs with 2n nodes.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A322659 Number of connected regular simple graphs on n labeled vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A272905 Number of connected 4-regular (or quartic) labeled graphs with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula