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

Author

Natan Arie Consigli, Dec 17 2019

Keywords

• nonn
• tabl
• hard

Comments

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

Examples

			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, ...
  ...
		

Links

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

Crossrefs

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.

Programs

nauty

# 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

Formula

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