# Non-isomorphic connected, unicyclic graphs

The question is: Find the number of non-isomorphic connected, unicyclic graphs(graphs with exactly one cycle) on 6 vertices.

According to this question does it mean that there is a general formula that enable us to find the number of non-isomorphic connected, unicyclic graphs on n vertices so that for vertices 6 may be particular?

This task doesn't suggest the existence of such a formula.

However, you can find a general formula for the number of non-isomorphic connected unicyclic graphs on $$n$$ vertices and specify it for $$n=6$$ to get the result.

But you can as well just count such graphs for $$n=6$$ directly.

• As I think hexagon is the only non-isomorphic connected unicyclic graphs on 6 vertices. Is that not? – 2468 Nov 10 '18 at 13:58
• No, you can have a smaller cycle as well. – Jakob B. Nov 10 '18 at 14:14

Using the notation from Analytic Combinatorics we have for the combinatorial class $$\mathcal{U}$$ of unicyclic non-isomorphic graphs the equation (we are attaching trees to the nodes of the single cycle where the root of the tree is merged into the cycle)

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{U} = \textsc{DHD}_{\ge 3}(\mathcal{T})$$

where $$\mathcal{T}$$ is the class of unlabeled rooted trees:

$$\mathcal{T} = \mathcal{Z} \times \textsc{MSET}(\mathcal{T})$$

Here we have used the dihedral operator for the single cycle (which is a bracelet i.e. a necklace that can be turned over) and the unlabeled multiset operator. The class equation for trees immediately yields a functional equation via the exponential formula, and which is

$$T(z) = z \exp\left(\sum_{\ell\ge 1} \frac{T(z^\ell)}{\ell}\right).$$

It was proved at the following MSE link using this functional equation that these have recurrence

$$t_{n+1} = \frac{1}{n} \sum_{q=1}^{n} t_{n+1-q} \left(\sum_{\ell|q} \ell t_{\ell}\right).$$

Using the cycle index $$Z(D_q)$$ of the dihedral group we have

$$U(z) = \sum_{q\ge 3} Z(D_q; T(z)).$$

Therefore the number of non-isomorphic connected unicyclic graphs is

$$U_n = [z^n] \sum_{q=3}^n Z\left(D_q; \sum_{p=1}^n t_p z^p\right).$$

This yields the sequence

$$0, 0, 1, 2, 5, 13, 33, 89, 240, 657, 1806, 5026, 13999, \\ 39260, 110381, 311465, 880840, 2497405, 7093751, 20187313, \ldots$$

with two leading zeros because the smallest cycle is on three nodes. The data point to OEIS A001429 where the procedure is confirmed. In particular we get for six nodes

$$\bbox[5px,border:2px solid #00A000]{ U_6 = 13.}$$

Remark. The cycle index of the cyclic group is given by

$$Z(C_q) = \frac{1}{q} \sum_{k|q} \phi(k) a_k^{q/k}$$

and of the dihedral group

$$Z(D_q) = \frac{1}{2} Z(C_q) + \begin{cases} \frac{1}{2} a_1 a_2^{(q-1)/2} & q \quad \text{odd} \\ \frac{1}{4} \left( a_1^2 a_2^{(q-2)/2} + a_2^{q/2} \right) & q \quad\text{even.} \end{cases}.$$

This computation was done with the following Maple code.

with(numtheory);

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

res := ind;

polyvars := indets(poly);
indvars := indets(ind);

for v in indvars do
pot := op(1, v);

subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];

subs2 := [v=subs(subs1, poly)];

res := subs(subs2, res);
od;

res;
end;

pet_cycleind_cyclic :=
proc(n)
local s, d;

s := 0;
for d in divisors(n) do
s := s + phi(d)*a[d]^(n/d);
od;

s/n;
end;

pet_cycleind_dihedral :=
proc(n)
local s;

s := 1/2*pet_cycleind_cyclic(n);

if type(n, odd) then
s := s + 1/2*a[1]*a[2]^((n-1)/2);
else
s := s + 1/4*(a[1]^2*a[2]^((n-2)/2) + a[2]^(n/2));
fi;

s;
end;

t :=
proc(n)
option remember;

if n=1 then return 1 fi;

q=1..n-1);
end;

U :=
proc(n)
option remember;
local res, m, tgf, dhdgf;

res := 0;

for m from 3 to n do
dhdgf :=
pet_varinto_cind(tgf, pet_cycleind_dihedral(m));
res := res +
coeff(expand(dhdgf), z, n);
od;

res;
end;


Addendum. We can also answer the question for the labeled case. The combinatorial classes are the same, only now we get the classic tree function $$T(z)$$ using

$$\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$

and functional equation

$$T(z) = z \times \exp T(z)$$

and the dihedral operator becomes

$$\sum_{\ell\ge 3} \frac{z^\ell}{|D_\ell|} = \sum_{\ell\ge 3} \frac{z^{\ell}}{2\ell} = -\frac{1}{2} z - \frac{1}{4} z^2 + \frac{1}{2} \log \frac{1}{1-z}.$$

We are thus interested in extracting the coefficient as follows,

$$n! [z^n] \left(-\frac{1}{2} T(z) - \frac{1}{4} T(z)^2 + \frac{1}{2} \log \frac{1}{1-T(z)}\right).$$

This has three components, the first is by Cayley

$$- n! [z^n] \frac{1}{2} T(z) = -\frac{1}{2} n^{n-1}.$$

The second is

$$- n! [z^n] \frac{1}{4} T(z)^2 = - (n-1)! [z^{n-1}] \frac{1}{2} T(z) T'(z) \\ = -\frac{(n-1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} \frac{1}{2} T(z) T'(z) \; dz.$$

Letting $$w=T(z)$$ so that $$z= w \exp(-w)$$ and $$dw = T'(z) \; dz$$ this becomes for $$n\ge 2$$

$$-\frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(nw)}{w^n} \frac{1}{2} w \; dw = - \frac{(n-1)!}{2} \frac{n^{n-2}}{(n-2)!} \\ = - \frac{1}{2} (n-1) n^{n-2}.$$

Finally for the third one we get

$$n! [z^n] \frac{1}{2} \log\frac{1}{1-T(z)} = (n-1)! [z^{n-1}] \frac{1}{2} \frac{1}{1-T(z)} T'(z) \\ = \frac{(n-1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^n} \frac{1}{2} \frac{1}{1-T(z)} T'(z) \; dz.$$

With the same substitution as before we find

$$\frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(nw)}{w^n} \frac{1}{2} \frac{1}{1-w} \; dw \\ = \frac{1}{2} (n-1)! \sum_{q=0}^{n-1} \frac{n^q}{q!}.$$

Collecting everything we obtain

$$\frac{1}{2} (n-1)! \sum_{q=0}^{n-1} \frac{n^q}{q!} - n^{n-1} + \frac{1}{2} n^{n-2}$$

or alternatively

$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{2} (n-1)! \sum_{q=0}^{n-3} \frac{n^q}{q!}.}$$

This sequence is OEIS A057500:

$$0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840, \\ 25201854045, 787368574080, 26667815195274, 973672928417280, \ldots$$