Generating function for non-isomorphic regular graphs.

Question

Determine a generating function for the number of non-isomorphic (n−2)-regular graphs of order n, for n ≥ 2.

I've been staring at this for hours and can't find a place to start, any help would be appreciated.

Answer 1

We enumerate the complements, namely non-isomorphic 2-regular graphs. These are sets of cycles and we find

$$\prod_{k\ge 3} \frac{1}{1-z^k} = (1-z)(1-z^2) \prod_{k\ge 1} \frac{1}{1-z^k}.$$

The term $1/(1-z^k)$ is the OGF of zero, one, two, three etc. instances of a cycle of order $k.$

This is the OGF

$$(1-z-z^2+z^3) \prod_{k\ge 1} \frac{1}{1-z^k}.$$

Using the partition function we get for $n\ge 3$

$$p(n) - p(n-1) - p(n-2) + p(n-3).$$

We obtain the sequence

$$1, 1, 1, 2, 2, 3, 4, 5, 6, 9, 10, 13, \\ 17, 21, 25, 33, 39, 49, \ldots$$

which points us to OEIS A00843, where these data are confirmed (indeed we have non-isomorphic 2-regular graphs).

For the case where the graphs are labeled we again have sets of cycles (with dihedral symmetry):

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\textsc{DHD}_{=3}(\mathcal{Z}) + \textsc{DHD}_{=4}(\mathcal{Z}) + \textsc{DHD}_{=5}(\mathcal{Z}) + \cdots).$$

This gives the EGF

$$\exp \left(\frac{1}{2} \frac{z^3}{3} +\frac{1}{2} \frac{z^4}{4} +\frac{1}{2} \frac{z^5}{5}+\cdots\right) \\ = \exp\left(-\frac{1}{2} z - \frac{1}{2} \frac{z^2}{2} + \frac{1}{2} \log\frac{1}{1-z}\right) \\ = \frac{1}{\sqrt{1-z}} \exp\left(-\frac{z}{2}-\frac{z^2}{4}\right).$$

We get the sequence starting at $n\ge 3$:

$$1, 3, 12, 70, 465, 3507, 30016, 286884, 3026655, \\ 34944085, 438263364, 5933502822, 86248951243, \ldots$$

which points us to OEIS A001205, where we get confirmation of these data once more.