A334546 -id:A334546 - cp's OEIS frontend

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 4, 5, 3, 1, 1, 1, 5, 8, 10, 3, 1, 1, 1, 6, 14, 26, 16, 4, 1, 1, 1, 7, 20, 61, 60, 29, 4, 1, 1, 1, 8, 30, 128, 243, 184, 45, 5, 1, 1, 1, 9, 40, 254, 800, 1228, 488, 75, 5, 1, 1, 1, 10, 55, 467, 2518, 7252, 6684, 1509, 115, 6, 1

Offset: 0

Andrew Howroyd, Apr 08 2020

T(n,k) is the number of non-isomorphic n X n nonnegative integer symmetric matrices with all row and column sums equal to k and isomorphism being up to simultaneous permutation of rows and columns. The case that allows independent permutations of rows and columns is covered by A333737.

Terms may be computed without generating each graph by enumerating the graphs by degree sequence using dynamic programming. A PARI program showing this technique for the labeled case is given in A188403. Burnside's lemma as applied in A192517 can be used to extend this method to the unlabeled case.

			Array begins:
==============================================
n\k | 0 1  2   3    4     5      6       7
----+-----------------------------------------
  0 | 1 1  1   1    1     1      1       1 ...
  1 | 1 1  1   1    1     1      1       1 ...
  2 | 1 2  3   4    5     6      7       8 ...
  3 | 1 2  5   8   14    20     30      40 ...
  4 | 1 3 10  26   61   128    254     467 ...
  5 | 1 3 16  60  243   800   2518    6999 ...
  6 | 1 4 29 184 1228  7252  38194  175369 ...
  7 | 1 4 45 488 6684 78063 772243 6254652 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..377 (antidiagonals 0..26)

Rows n=0..4 are A000012, A000012, A000027(n+1), A006918(n+1), A333897.
Columns k=0..5 are A000012, A008619, A000990, A333894, A333895, A333896.
Cf. A188403, A192517, A263293, A333161, A333330, A333737, A334546.

A243391 Number of isomorphism classes of connected 3-regular loopless multigraphs with n vertices and with semi-edges allowed.

Original entry on oeis.org

1, 3, 4, 12, 22, 68, 166, 534, 1589, 5464, 18579, 68320, 255424, 1000852, 4018156, 16671976, 70890940, 309439942, 1381815168, 6310880471, 29428287639, 140012980007, 678970863717, 3353545264060, 16857749613964, 86191265140699, 447951112379963, 2365177154077186

Offset: 1

Nico Van Cleemput, Jun 04 2014

nonn

a(n) is also the number of isomorphism classes of connected loopless multigraphs with n vertices of degree 3 or less. - Andrew Howroyd, Mar 20 2020

Nino Bašić and Ivan Damnjanović, On cubic polycirculant nut graphs, arXiv:2411.16904 [math.CO], 2024. See p. 22.
Gunnar Brinkmann, Nico Van Cleemput, and Tomaž Pisanski, Generation of various classes of trivalent graphs, Theoretical Comp. Sci. (2013) Vol. 502, 16-29.

Column k=3 of A334546.

Cf. A000421, A243392, A243393, A243394, A303030.

a(23)-a(28) from Andrew Howroyd, Mar 20 2020

A289157 Number of unlabeled connected loopless multigraphs with n nodes of degree 4 or less.

Original entry on oeis.org

1, 1, 4, 9, 37, 146, 772, 4449, 30307, 228605, 1921464, 17652327, 176162548, 1893738334, 21806975279, 267636988052, 3486370839295, 48029272657002, 697542580286159, 10649954607360119, 170508064788069346, 2856122791685125616, 49951625299057923405

Offset: 0

Natan Arie Consigli, Jul 04 2017

nonn

Column k=4 of A334546.
Cf. A121941 (single edges only), A134818 (with no more than triple edges), A289158 (with no more than double edges).
Cf. A243391 (degree 3 or less).

nauty
```
geng -c -D4 ${n} -q | multig -D4 -u
```

a(18)-a(22) from Andrew Howroyd, Mar 20 2020

A289988 Number of unlabeled connected loopless multigraphs with n nodes of degree n or less.

Original entry on oeis.org

1, 1, 2, 4, 37, 602, 34126, 6021463, 3616906549, 7361925161868, 51324462383008758, 1240420936122453106498, 105141919479926837860474091, 31581183353539008502807807352728

Offset: 0

Natan Arie Consigli, Aug 19 2017

Multigraphs are loopless.

Main diagonal of A334546.

Cf. A007719, A076864, A134818, A289157, A289158, A289987.

for n in {1..8}; do geng -c -D${n} ${n} -q | multig -m$[${n}-1] -D$[${n}-1] -u; done

a(0) corrected and a(9)-a(13) from Andrew Howroyd, May 05 2020

A289987 Number of unlabeled connected loopless multigraphs with n nodes of degree less than n.

Original entry on oeis.org

0, 1, 1, 2, 12, 146, 5847, 716141, 300635753, 430472002801, 2117649544384420, 36154420408979339192, 2165755991529764630384554, 459803603042851200545393118005

Offset: 0

Natan Arie Consigli, Aug 19 2017

Multigraphs are loopless.

			From _Gheorghe Coserea_, Oct 11 2017: (Start)
For n=4 the a(4)=12 solutions are:
o--o--o--o   o==o--o--o   o--o==o--o   o==o--o==o
o--o         o==o         o==o
|  |         |  |         |  |
o--o         o--o         o==o
o--o         o==o
| /          | /
|/           |/
o--o         o--o
o---o        o--o         o--o--o
|\ /|        | /|            |
| x |        |/ |            o
|/ \|        o--o
o---o
(End)

A diagonal of A334546.

Cf. A001349, A289988.

for n in {1..8}; do geng -c -D$[${n}-1] ${n} -q | multig -m$[${n}-1] -D$[${n}-1] -u; done

a(9)-a(13) from Andrew Howroyd, May 05 2020

A334547 Number of unlabeled connected loopless multigraphs with n nodes of degree 5 or less.

Original entry on oeis.org

1, 1, 5, 14, 93, 602, 5847, 66289, 937696, 15575285, 301360805, 6663874305, 166516898890, 4654082023569, 144301649717895, 4928171085359360, 184252862642720722, 7501009857590958129, 330928677041195111955, 15754816518916261088582, 806306082299053607173143

Offset: 0

Andrew Howroyd, May 05 2020

nonn

Column k=5 of A334546.

Cf. A303031, A303032, A303033, A333896.

Inverse Euler transform of A333896.

cp's OEIS Frontend

A333893 Array read by antidiagonals: T(n,k) is the number of unlabeled loopless multigraphs with n nodes of degree k or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A243391 Number of isomorphism classes of connected 3-regular loopless multigraphs with n vertices and with semi-edges allowed.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A289157 Number of unlabeled connected loopless multigraphs with n nodes of degree 4 or less.

Views

Author

Keywords

Crossrefs

Programs

nauty

Extensions

A289988 Number of unlabeled connected loopless multigraphs with n nodes of degree n or less.

Views

Author

Keywords

Comments

Crossrefs

Programs

nauty

Extensions

A289987 Number of unlabeled connected loopless multigraphs with n nodes of degree less than n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

nauty

Extensions

A334547 Number of unlabeled connected loopless multigraphs with n nodes of degree 5 or less.

Views

Author

Keywords

Crossrefs

Formula