2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\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.