A289986 -id:A289986 - 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

A319897 Number of connected regular loopless multigraphs on n unlabeled nodes with degree up to n.

Original entry on oeis.org

1, 1, 2, 1, 6, 7, 195, 984, 648947, 35494648, 689162614688, 250087643676776, 116889497942206867366

Offset: 0

Natan Arie Consigli, Nov 28 2018

Initial terms computed using 'Nauty and Traces'.

Brendan McKay and Adolfo Piperno, Nauty and Traces

Cf. A289986, A325476, A328682.

a(n) = Sum_{k=0..n} A328682(n, k). - Andrew Howroyd, Mar 18 2020

a(1), a(8) corrected and a(10)-a(12) added by Andrew Howroyd, Mar 18 2020

A319896 Number of connected non-regular multigraphs with n nodes of degree up to n.

Original entry on oeis.org

0, 1, 0, 3, 31, 595, 33931, 6020479, 3613415171

Offset: 0

Natan Arie Consigli, Sep 30 2018

Multigraphs are loopless.

Terms computed using nauty traces.

Brendan McKay and Adolfo Piperno, Nauty traces

Cf. A289988, A289986, A319897.

a(n) = A289988(n) - A319897(n).

A325476 Number of connected regular loopless multigraphs on n unlabeled nodes of degree less than n.

Original entry on oeis.org

1, 1, 1, 1, 3, 7, 75, 984, 105831, 35494648, 53493557150, 250087643676776, 4520743153498327817, 272584534800111470995411

Offset: 0

Natan Arie Consigli, May 02 2019

Multigraphs are loopless.

Initial terms computed using nauty and traces.

			There is no such thing as a graph with nodes of negative degree, and the "nodeless" graph has, according to the definition in the name, zero nodes of degree less than 0. So a(0) = 1.

Brendan McKay and Adolfo Piperno, Nauty and Traces

Cf. A289988, A289986, A319896, A319897, A324218, A325474, A328682.

for ((n=2; n<9; n++)); do
a=0
for ((d=0; d<${n}; d++)); do
s=$(geng -c -d1 ${n} -q | multig -r${d} -u 2>&1 | cut -d ' ' -f 7 | grep -v '^$')
a=$((a+s))
done
echo ${a}
done
# Andrey Zabolotskiy, Sep 26 2019

a(n) = Sum_{k=0..n-1} A328682(n, k). - Andrew Howroyd, Mar 18 2020

a(10)-a(13) from Andrew Howroyd, Mar 18 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

A319897 Number of connected regular loopless multigraphs on n unlabeled nodes with degree up to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A319896 Number of connected non-regular multigraphs with n nodes of degree up to n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A325476 Number of connected regular loopless multigraphs on n unlabeled nodes of degree less than n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

nauty

Formula

Extensions