A129417 -id:A129417 - cp's OEIS frontend

A006820 Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.

1, 0, 0, 0, 0, 1, 1, 2, 6, 16, 59, 265, 1544, 10778, 88168, 805491, 8037418, 86221634, 985870522, 11946487647, 152808063181, 2056692014474, 29051272833609, 429668180677439, 6640165204855036, 107026584471569605, 1796101588825595008, 31333997930603283531, 567437240683788292989

Offset: 0

N. J. A. Sloane

The null graph on 0 vertices is vacuously connected and 4-regular. - Jason Kimberley, Jan 29 2011
The Multiset Transform of this sequence gives a triangle which gives in row n and column k the 4-regular simple graphs with n>=1 nodes and k>=1 components (row sums A033301), starting:
;
;
;
;
1 ;
1 ;
2 ;
6 ;
16 ;
59 1 ;
265 1 ;
1544 3 ;
10778 8 ;
88168 25 ;
805491 87 1 ;
8037418 377 1 ;
86221634 2023 3 ;
985870522 13342 9 ;
11946487647 104568 27 ;
152808063181 930489 96 1 ;  - R. J. Mathar, Jun 02 2022

CRC Handbook of Combinatorial Designs, 1996, p. 648.
I. A. Faradzev, Constructive enumeration of combinatorial objects, pp. 131-135 of Problèmes combinatoires et théorie des graphes (Orsay, 9-13 Juillet 1976). Colloq. Internat. du C.N.R.S., No. 260, Centre Nat. Recherche Scient., Paris, 1978.
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).

Wayne Barrett, Shaun Fallat, Veronika Furst, Shahla Nasserasr, Brendan Rooney, and Michael Tait, Regular Graphs of Degree at most Four that Allow Two Distinct Eigenvalues, arXiv:2305.10562 [math.CO], 2023. See p. 7.
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. [_Jason Kimberley_, Nov 24 2009]
M. Meringer, GenReg, Generation of regular graphs, program.
Markus Meringer, H. James Cleaves, Stephen J. Freeland, Beyond Terrestrial Biology: Charting the Chemical Universe of α-Amino Acid Structures, Journal of Chemical Information and Modeling, 53.11 (2013), pp. 2851-2862.
Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Quartic Graph
Eric Weisstein's World of Mathematics, Regular Graph
Zhipeng Xu, Xiaolong Huang, Fabian Jimenez, and Yuefan Deng, A new record of enumeration of regular graphs by parallel processing, arXiv:1907.12455 [cs.DM], 2019.

From Jason Kimberley, Mar 27 2010 and Jan 29 2011: (Start)
4-regular simple graphs: this sequence (connected), A033483 (disconnected), A033301 (not necessarily connected).
Connected regular simple graphs: A005177 (any degree), A068934 (triangular array); specified degree k: A002851 (k=3), this sequence (k=4), A006821 (k=5), A006822 (k=6), A014377 (k=7), A014378 (k=8), A014381 (k=9), A014382 (k=10), A014384 (k=11).
Connected 4-regular simple graphs with girth at least g: this sequence (g=3), A033886 (g=4), A058343 (g=5), A058348 (g=6).
Connected 4-regular simple graphs with girth exactly g: A184943 (g=3), A184944 (g=4), A184945 (g=5).
Connected 4-regular graphs: this sequence (simple), A085549 (multigraphs with loops allowed), A129417  (multigraphs with loops verboten). (End)

a(n) = A184943(n) + A033886(n).
a(n) = A033301(n) - A033483(n).
Inverse Euler transform of A033301.
Row sums of A184940. - R. J. Mathar, May 30 2022

a(19)-a(22) were appended by Jason Kimberley on Sep 04 2009, Nov 24 2009, Mar 27 2010, and Mar 18 2011, from running M. Meringer's GENREG for 3.4, 44, and 403 processor days, and 15.5 processor years, at U. Ncle.

a(22) corrected and a(23)-a(28) from Andrew Howroyd, Mar 10 2020

A328682 Array read by antidiagonals: T(n,r) is the number of connected r-regular loopless multigraphs on n unlabeled nodes.

Original entry on oeis.org

1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 2, 1, 0, 0, 1, 0, 1, 0, 3, 0, 1, 0, 0, 1, 0, 1, 1, 4, 6, 6, 1, 0, 0, 1, 0, 1, 0, 6, 0, 19, 0, 1, 0, 0, 1, 0, 1, 1, 7, 15, 49, 50, 20, 1, 0, 0, 1, 0, 1, 0, 9, 0, 120, 0, 204, 0, 1, 0, 0, 1, 0, 1, 1, 11, 36, 263, 933, 1689, 832, 91, 1, 0, 0, 1, 0, 1, 0, 13, 0, 571, 0, 13303, 0, 4330, 0, 1, 0, 0, 1, 0, 1, 1, 15, 72, 1149, 12465, 90614, 252207, 187392, 25227, 509, 1, 0, 0

Offset: 0

Natan Arie Consigli, Dec 17 2019

Initial terms computed using 'Nauty and Traces' (see the link).
T(0,r) = 1 because the "nodeless" graph has zero (therefore in this case all) nodes of degree r (for any r).
T(1,0) = 1 because only the empty graph on one node is 0-regular on 1 node.
T(1,r) = 0, for r>0: there's only one node and loops aren't allowed.
T(2,r) = 1, for r>0 since the only edges that are allowed are between the only two nodes.
T(3,r) = parity of r, for r>0. There are no such graphs of odd degree and for an even degree the only multigraph satisfying that condition is the regular triangular multigraph.
T(n,0) = 0, for n>1 because graphs having more than a node of degree zero are disconnected.
T(n,1) = 0, for n>2 since any connected graph with more than two nodes must have a node of degree greater than two.
T(n,2) = 1, for n>1: the only graphs satisfying that condition are the cyclic graphs of order n.
This sequence may be derived from A333330 by inverse Euler transform. - Andrew Howroyd, Mar 15 2020

			Square matrix T(n,r) begins:
========================================================
n\r | 0     1     2     3     4     5      6      7
----+---------------------------------------------------
  0 | 1,    1,    1,    1,    1,    1,     1,     1, ...
  1 | 1,    0,    0,    0,    0,    0,     0,     0, ...
  2 | 0,    1,    1,    1,    1,    1,     1,     1, ...
  3 | 0,    0,    1,    0,    1,    0,     1,     0, ...
  4 | 0,    0,    1,    2,    3,    4,     6,     7, ...
  5 | 0,    0,    1,    0,    6,    0,    15,     0, ...
  6 | 0,    0,    1,    6,   19,   49,   120,   263, ...
  7 | 0,    0,    1,    0,   50,    0,   933,     0, ...
  8 | 0,    0,    1,   20,  204, 1689, 13303, 90614, ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..350
Brendan McKay and Adolfo Piperno, Nauty and Traces

Rows n=3..9 are: A000035, A253186, A324221, A324218, A324217, A325474, A327604.
Columns r=3..8 are: A000421, A129417, A129419, A129421, A129423, A129425.
Cf. A289986 (main diagonal), A333330 (not necessarily connected), A333397.

# This program will execute the "else echo" line if the graph is nontrivial (first three columns, first two rows or both row and column indices are odd)
for ((i=0; i<16; i++)); do
n=0
r=${i}
while ((n<=i)); do
if( (((r==0)) && ((n==0)) ) || ( ((r==0)) && ((n==1)) ) || ( ((r==1)) && ((n==2)) ) || ( ((r==2)) && !((n==1)) ) ); then
echo 1
elif( ((n==0)) || ((n==1)) || ((r==0)) || ((r==1)) || (! ((${r}%2 == 0)) && ! ((${n}%2 == 0)) || ( ((r==2)) && ((n==1)) )) ); then
echo 0
else echo $(./geng -c -d1 ${n} -q | ./multig -m${r} -r${r} -u 2>&1 | cut -d ' ' -f 7 | grep -v '^$');  fi;
((n++))
((r--))
done
done

Column r is the inverse Euler transform of column r of A333330. - Andrew Howroyd, Mar 15 2020

A000421 Number of isomorphism classes of connected 3-regular (trivalent, cubic) loopless multigraphs of order 2n.

Original entry on oeis.org

1, 2, 6, 20, 91, 509, 3608, 31856, 340416, 4269971, 61133757, 978098997, 17228295555, 330552900516, 6853905618223, 152626436936272, 3631575281503404, 91928898608055819, 2466448432564961852, 69907637101781318907

Offset: 1

N. J. A. Sloane

a(n) is also the number of isomorphism classes of connected 3-regular simple graphs of order 2n with possibly loops. - Nico Van Cleemput, Jun 04 2014

There are no graphs of order 2n+1 satisfying the condition above. - Natan Arie Consigli, Dec 20 2019

			From _Natan Arie Consigli_, Dec 20 2019: (Start)
a(1) = 1: with two nodes the only viable option is the triple edged path multigraph.
a(2) = 4: with four nodes we have two cases: the tetrahedral graph and the square graph with single and double edges on opposite sides.
(End)

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 92 [gives incorrect a(6)].
CRC Handbook of Combinatorial Designs, 1996, p. 651 [or: 2006, table 4.40].

Jan-Peter Börnsen, Anton E. M. van de Ven, Tangent Developable Orbit Space of an Octupole, arXiv:1807.04817 [hep-th], 2018.
G. Brinkmann, N. Van Cleemput, T. Pisanski, Generation of various classes of trivalent graphs, Theoretical Computer Science 502, 2013, pp.16-29.
R. J. Mathar, Cubic multigraphs A000421
Brendan McKay and others, Nauty Traces

Column k=3 of A328682 (table of k-regular n-node multigraphs).

Cf. A129416, A005967 (loops allowed), A129417, A129419, A129421, A129423, A129425, A002851 (no multiedges).

for n in {1..10}; do geng -cqD3 $[2*$n] | multig -ur3; done # Sean A. Irvine, Sep 24 2015

Inverse Euler transform of A129416. - Andrew Howroyd, Mar 19 2020

More terms from Brendan McKay, Apr 15 2007

a(13)-a(20) from Andrew Howroyd, Mar 19 2020

A085549 Number of isomorphism classes of connected 4-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 2, 4, 10, 28, 97, 359, 1635, 8296, 48432, 316520, 2305104, 18428254, 160384348, 1506613063, 15180782537, 163211097958, 1864251304892, 22540603640086, 287577260214946, 3860595341568062, 54397355465967057, 802684717378090204

Offset: 1

Benjamin A. Burton (bab(AT)debian.org), Jul 04 2003

Also the number of different potential face pairing graphs for closed 3-manifold triangulations.

Computed from A129429 by an inverse Euler transform. - R. J. Mathar, Mar 09 2019

B. A. Burton, Minimal triangulations and face pairing graphs, preprint, 2003.

Andrew Howroyd, Table of n, a(n) for n = 1..40
B. A. Burton, Regina (3-manifold topology software).
B. A. Burton, Minimal triangulations and normal surfaces, Ph.D. thesis, University of Melbourne, 2003.
B. A. Burton, Face pairing graphs and 3-manifold enumeration, arXiv:math/0307382 [math.GT], 2003.
B. A. Burton, Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find, Discrete and Computational Geometry, 38 (2007), 527-571.
R. de Mello Koch, S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007
H. Kleinert, A. Pelster, B. Kastening, M. Bachmann, Recursive graphical construction of Feynman diagrams and their multiplicities in Phi^4 and Phi^2*A theory, Phys. Rev. E 62 (2) (2000), 1537 eq (4.20) or arXiv:hep-th/9907168, 1999.
B. Martelli and C. Petronio, Three-manifolds having complexity at most 9, Experiment. Math., Vol. 10 (2001), pp. 207-236
R. J. Mathar, Illustrations

Column k=4 of A333397.

Cf. A129429, A129417, A005967, A129430, A129432, A129434, A129436, A118560.

A129429 = Cases[Import["https://oeis.org/A129429/b129429.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A129429] (* Jean-François Alcover, Dec 03 2019, updated Mar 17 2020 *)

Inverse Euler transform of A129429.

a(12)-a(16) from Brendan McKay, Apr 15 2007, computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/
Edited by N. J. A. Sloane, Oct 01 2007
a(17)-a(23) from A129429 from Jean-François Alcover, Dec 03 2019

A129419 Number of isomorphism classes of connected 5-regular loopless multigraphs of order 2n.

Original entry on oeis.org

1, 4, 49, 1689, 187392, 46738368, 20446754006, 14021056991357, 14141140657400321, 20047531681346319557, 38567298550226625579671, 97861817259606311572409609, 319914449561753621623849929222, 1320949150506412557504787822889933, 6773751604973857152218372443743552754

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Brendan McKay and Adolfo Piperno, Nauty and Traces

Column k=5 of A328682.

Cf. A129420, A129430, A000421, A129417, A129421, A129423, A129425, A328682.

geng -c -d1 $[2*$n] -q | multig -r5 -u # Natan Arie Consigli, Dec 20 2019

Inverse Euler transform of A129420. - Andrew Howroyd, Mar 17 2020

a(8)-a(15) from Andrew Howroyd, Mar 21 2020

A129421 Number of isomorphism classes of connected 6-regular loopless multigraphs of order n.

Original entry on oeis.org

0, 1, 1, 6, 15, 120, 933, 13303, 252207, 6450828, 205475039, 7936493756, 363639228194, 19476976825809, 1205115679461426, 85288127619421544, 6845235025444882069, 618411485467843477405, 62471139399366989007575, 7014991719815977343879171

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Brendan McKay and Adolfo Piperno, Nauty and Traces

Column k=6 of A328682.

Cf. A129422, A129432, A000421, A129417, A129419, A129423, A129425, A328682.

geng -c -d1 ${n} -q | multig -r6 -u # Natan Arie Consigli, Jun 05 2017

Inverse Euler transform of A129422. - Andrew Howroyd, Mar 17 2020

a(1)=0 prepended and a(14)-a(20) from Andrew Howroyd, Mar 17 2020

A129425 Number of isomorphism classes of connected 8-regular loopless multigraphs of order n.

Original entry on oeis.org

0, 1, 1, 9, 36, 571, 12465, 543116, 35241608, 3230417239, 397514307014, 63830872225605, 13080448625309965, 3358687593761378470, 1063838242661288090062, 410057057694777406364151, 190064879184725871853627854, 104825763290631293396894238206

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Brendan McKay and Adolfo Piperno, Nauty and Traces

Column k=8 of A328682.

Cf. A129426, A129436, A000421, A129417, A129419, A129421, A129423, A328682.

geng -c -d1 ${n} -q | multig -r8 -u # Natan Arie Consigli, Jun 05 2017

Inverse Euler transform of A129426. - Andrew Howroyd, Mar 17 2020

Deleted a(0) and a(1). - N. J. A. Sloane, Jan 11 2020

a(1)=0 prepended and a(12)-a(18) from Andrew Howroyd, Mar 17 2020

A129418 Number of isomorphism classes of 4-regular loopless multigraphs of order n.

Original entry on oeis.org

1, 0, 1, 1, 4, 7, 24, 60, 240, 930, 4701, 26637, 178569, 1339529, 11187064, 101871881, 1002594996, 10574095327, 118850827173, 1417140114336, 17860018997346, 237160827107408, 3309078044759285, 48396906463199522, 740331404753448181, 11821525310570525197

Offset: 0

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Also number of carbon allotropes satisfying the octet rule, excluding stereoisomers. - Natan Arie Consigli, Jun 06 2017

Column k=4 of A333330.

Cf. A129417, A129429, A129416, A129420, A129422, A129424, A129426.

geng -d1 ${n} -q | multig -r4 -u # Natan Arie Consigli, Jun 06 2017

Euler transform of A129417. - Andrew Howroyd, Mar 14 2020

a(0)-a(1) by Natan Arie Consigli, Jun 06 2017

a(18)-a(25) from Andrew Howroyd, Mar 17 2020

A129423 Number of isomorphism classes of connected 7-regular loopless multigraphs of order 2n.

Original entry on oeis.org

1, 7, 263, 90614, 165041329, 861723619902, 10351918806321621, 253216618556625008961, 11542463442106815907796586, 915449471830886733265105097578

Offset: 1

Brendan McKay, Apr 15 2007

nonn

Initial terms computed using software at http://users.cecs.anu.edu.au/~bdm/nauty/

Brendan McKay and Adolfo Piperno, Nauty and Traces

Column k=7 of A328682.

Cf. A129424, A129434, A000421, A129417, A129419, A129421, A129425, A328682.

geng -c -d1 $[2*$n] -q | multig -r7 -u # Natan Arie Consigli, Dec 20 2019

Inverse Euler transform of A129424. - Andrew Howroyd, Mar 21 2020

a(7)-a(10) from Andrew Howroyd, Mar 21 2020

A289986 Number of connected 2n-regular loopless multigraphs on 2n unlabeled nodes.

Original entry on oeis.org

1, 1, 3, 120, 543116, 635669057538, 112368754788708539549

Offset: 0

Natan Arie Consigli, Aug 19 2017

Multigraphs are loopless.

There are no (2n+1)-regular multigraphs with (2n+1) number of points, for every nonnegative n.

Cf. A005177, A129417, A129421, A129425, A328682.

for n in {1..4}; do geng -c -d1 $[2*$n] -q | multig -m$[2*$n] -r$[2*$n] -u; done

a(n) = A328682(2*n, 2*n). - Andrew Howroyd, Mar 18 2020

a(5)-a(6) from Andrew Howroyd, Mar 18 2020

cp's OEIS Frontend

A006820 Number of connected regular simple graphs of degree 4 (or quartic graphs) with n nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A328682 Array read by antidiagonals: T(n,r) is the number of connected r-regular loopless multigraphs on n unlabeled nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

A000421 Number of isomorphism classes of connected 3-regular (trivalent, cubic) loopless multigraphs of order 2n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

nauty

Formula

Extensions

A085549 Number of isomorphism classes of connected 4-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A129419 Number of isomorphism classes of connected 5-regular loopless multigraphs of order 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Formula

Extensions

A129421 Number of isomorphism classes of connected 6-regular loopless multigraphs of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Formula

Extensions

A129425 Number of isomorphism classes of connected 8-regular loopless multigraphs of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

nauty

Formula

Extensions