A333397 -id:A333397 - cp's OEIS frontend

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

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

A005967 Number of isomorphism classes of connected 3-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

2, 5, 17, 71, 388, 2592, 21096, 204638, 2317172, 30024276, 437469859, 7067109598, 125184509147, 2410455693765, 50101933643655, 1117669367609605, 26629298567576331, 674793598023809924, 18119844622209998036

Offset: 1

N. J. A. Sloane

nonn

a(n) is the number of maximal cells in the moduli space of tropical curves of genus n+1; see Melody Chan (2012) reference. a(n) is also the number of maximally degenerate stable nodal algebraic curves of genus n+1, up to isomorphism, by the association of a stable nodal curve to its dual graph. - Harry Richman, Oct 23 2023

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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. Brinkmann, N. Van Cleemput, and T. Pisanski, Generation of various classes of trivalent graphs, Theor. Comput. Sci. 502 (2013) 16-29, Table 1 column LM.
Melody Chan, Combinatorics of the tropical Torelli map, Algebra Number Theory, 6 (2012), 1133-1169.
Melody Chan, Moduli Spaces of Curves: Classical and Tropical, Notices Amer. Math. Soc., 68 (2021), 1700-1713.
R. de Mello Koch and S. Ramgoolam, Strings from Feynman graph counting: Without large N, Phys. Rev. D 85 (2012) 026007 (D7).
R. J. Mathar, Cubic Multigraphs A005967
R. J. Mathar, Feynman diagrams of the QED vacuum polarization, vixra:1901.0148 (2019).
Brendan McKay, nauty software
Wikipedia, Moduli of algebraic curves.

Column k=3 of A333397.

Cf. A129427 (Euler transf.), A000421 (no loops), A085549, A129430, A129432, A129434, A129436.

Inverse Euler transform of A129427.

Checked by Brendan McKay, Apr 15 2007
Using sequence A129427, terms a(12)-a(16) were computed in GAP by Ignat Soroko, Apr 07 2010
a(17)-a(19) added by 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

A167625 Square array T(n,k), read by upward antidiagonals, counting isomorphism classes of k-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 0, 2, 0, 1, 1, 3, 2, 1, 1, 0, 5, 0, 3, 0, 1, 1, 7, 8, 7, 3, 1, 1, 0, 11, 0, 20, 0, 4, 0, 1, 1, 15, 31, 56, 32, 13, 4, 1, 1, 0, 22, 0, 187, 0, 66, 0, 5, 0, 1, 1, 30, 140, 654, 727, 384, 101, 22, 5, 1, 1, 0, 42, 0, 2705, 0, 3369, 0, 181, 0, 6, 0, 1, 1, 56, 722, 12587, 42703

Offset: 1

Jason Kimberley, Nov 07 2009

The number of vertices n is positive; valency k is nonnegative.
Each loop contributes two to the valency of its vertex.
The antidiagonal having coordinate sum t=n+k is read from T(t,0) to T(1,t-1).
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 A333467. Burnside's lemma can be used to extend this method to the unlabeled case. - Andrew Howroyd, Mar 23 2020

			Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  1 | 1 0  1   0    1     0      1       0 ...
  2 | 1 1  2   2    3     3      4       4 ...
  3 | 1 0  3   0    7     0     13       0 ...
  4 | 1 1  5   8   20    32     66     101 ...
  5 | 1 0  7   0   56     0    384       0 ...
  6 | 1 1 11  31  187   727   3369   12782 ...
  7 | 1 0 15   0  654     0  40365       0 ...
  8 | 1 1 22 140 2705 42703 675368 8584767 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..378 (27 antidiagonals, first 19 antidiagonals from Jason Kimberley)
J. S. Kimberley, Table in user subpage of wiki.
R. C. Read, The enumeration of locally restricted graphs (I), J. London Math. Soc. 34 (1959) 417-436.

Column sequences: A000012 (k=0), A059841 (k=1), A000041 (k=2), A129427 (k=3), A129429 (k=4), A129431 (k=5), A129433 (k=6), A129435 (k=7), A129437 (k=8).

Cf. A333330 (loopless), A333397 (connected), A333467 (labeled).

T(n,k) = N\{S_n[S_k] * S_{nk/2}[S_2]\}.

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

3, 26, 639, 40264, 5846105, 1620621150, 752480161278, 538934691750368, 562620407713724992, 820458681175954269942, 1616087981640640784235446, 4183688192689449962777539596, 13914233045360143936837907106395, 58319096569220501055727735345999221

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=5 of A333397.

Cf. A129431, A129419, A005967, A085549, A129432, A129434, A129436.

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

a(8)-a(14) added by Andrew Howroyd, Mar 21 2020

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 3, 9, 47, 291, 2789, 35646, 622457, 14019433, 395208047, 13561118011, 555498075986, 26751985389463, 1496090275853092, 96154662330195078, 7038800665162854369, 582281978355495520076, 54057819690711609171892, 5597375885970846586170796, 642829784413912305507730345

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=6 of A333397.

Cf. A129433, A129421, A005967, A085549, A129430, A129434, A129436.

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

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

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Original entry on oeis.org

4, 91, 12398, 8530044, 20068725095, 122563246940846, 1657847267734501346, 44557979504639651662163, 2193071655191529316254072193, 185380797361862371952777763438426

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=7 of A333397.

Cf. A129435, A129423, A005967, A085549, A129430, A129432, A129436.

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

a(6)-a(10) added by Andrew Howroyd, Mar 21 2020

A129436 Number of isomorphism classes of connected 8-regular multigraphs of order n, loops allowed.

Original entry on oeis.org

1, 4, 17, 149, 1934, 44821, 1631629, 89057367, 6849428873, 713780361312, 97876276145119, 17259548258350637, 3840154740252625874, 1060662127742505706789, 358584059544008234423217, 146560585570176100774010071, 71630591614693085251230481320, 41456445821273701849195905028292

Offset: 1

Brendan McKay, Apr 15 2007

nonn

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

Column k=8 of A333397.

Cf. A129437, A129425, A005967, A085549, A129430, A129432, A129434.

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

a(11)-a(18) added by Andrew Howroyd, Mar 21 2020

cp's OEIS Frontend

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

A005967 Number of isomorphism classes of connected 3-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

A167625 Square array T(n,k), read by upward antidiagonals, counting isomorphism classes of k-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A129430 Number of isomorphism classes of connected 5-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129432 Number of isomorphism classes of connected 6-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129434 Number of isomorphism classes of connected 7-regular multigraphs of order 2n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A129436 Number of isomorphism classes of connected 8-regular multigraphs of order n, loops allowed.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions