Non-isomorphic connected, unicyclic graphs

Question

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?

Answer 1

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.

Answer 2

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;

    1/(n-1)*add(t(n-q)*add(l*t(l), l in divisors(q)),
                q=1..n-1);
end;

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

    tgf := add(t(p)*z^p, p=1..n);

    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$$

again with two leading zeros.