3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be put on hold. To prevent that, please edit the question. This will help you recognise and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers $\endgroup$ – The Demonix _ Hermit Oct 9 '19 at 10:10
  • $\begingroup$ You can start by drawing all the ones you can for relatively small values of $n$ so that you could form the start of a sequence to check with OEIS. $\endgroup$ – Matthew Daly Oct 9 '19 at 10:13
  • $\begingroup$ I'd enumerate the complements of the given graphs. $\endgroup$ – Chris Godsil Oct 9 '19 at 17:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.