5
$\begingroup$

Do graphs of the following sort have a specific name? We've been calling them Cactapillars, as they're cacti that look a little like caterpillars (and the name Caterpillar already refers to a different type of graph). They consist of k 4-cycles connected end to end, with possibly some leaves attached. If there's not a specific name for this type, do the versions of the graphs without leaves (i.e. just strings of connected 4-cycles) have a name?

Some sample "Cactapillars"

$\endgroup$
  • $\begingroup$ I'd call them centipedes ! (but there doesn't seem to be an official name) $\endgroup$ – Manuel Lafond Jun 26 '14 at 18:24
  • $\begingroup$ I agree, there probably isn't a name for these yet. Cacterpillar is nice. Centipede is already taken: mathworld.wolfram.com/Centipede.html $\endgroup$ – Perry Elliott-Iverson Jun 27 '14 at 13:26
1
$\begingroup$

Here are some observations concerning the enumeration of these graphs up to isomorphism. The OEIS doesn't seem to have an entry for the count yet so no verification and no error-proof results. Preliminary remark. We will call these cacterpillar centipedes and refer to them as centipedes throughout.

We consider the skeleton of the centipede into which we substitute bushels of leaves and use the Polya Enumeration Theorem to count these up to isomorphism. Therefore we need the cycle index $Z(Q_n)$ of the centipede consisting of $n$ copies of a $4$-cycle. (The slots for the application of PET are the nodes that have degree two.)

The automorphisms of the centiped are generated by a single flip about a vertical axis passing through the center and individual flips that exchange the top and bottom node of a $4$-cycle.

We now establish recurrences for the cycle index constituents of the two types of automorphisms. The first type $T$ is the flips of the top and bottom nodes of the $4$-cycles without the flip of the entire centipede that maps left to right. We obtain $$t_0 = 1, t_1 = \frac{1}{2} (a_1^2 + a_2) \quad\text{and}\quad t_n = t_{n-2} \times \frac{1}{4} (a_1^4 + 2 a_1^2 a_2 + a_2^2).$$ The above does not account for the two end nodes which we will treat at the end. The second type $S$ consists of a left-right exchanging flip combined with individual flips of top and bottom nodes of $4$-cycles. We obtain $$s_0 = 1, s_1 = \frac{1}{2} (a_1^2 + a_2) \quad\text{and}\quad s_n = s_{n-2} \times \frac{1}{4} (2 a_2^2 + 2 a_4).$$ Unrolling these very simple recurrences and doing the accounting we get $$t_{2n} = \frac{1}{2^{2n}} (a_1^2 + a_2)^{2n} \quad\text{and}\quad t_{2n+1} = \frac{1}{2^{2n+1}} (a_1^2 + a_2)^{2n+1}$$ which we may join to produce $$t_n = \frac{1}{2^n} (a_1^2 + a_2)^n.$$ For $s_n$ we obtain $$s_{2n} = \frac{1}{2^n} (a_2^2 + a_4)^n \quad\text{and}\quad s_{2n+1} = \frac{1}{2^{n+1}} (a_1^2+a_2) (a_2^2 + a_4)^n.$$

We are now ready to construct the cycle index of the centipede species $\mathfrak{Q}$ which is given by $$\sum_{n\ge 1} Z(Q_n) = \frac{1}{2} \sum_{n\ge 1} (a_1^2 t_n + a_2 s_n)$$ where we have included the terms for the outer two nodes.

The first term is easy to sum and works out to $$ - \frac{1}{2} a_1^2 + \frac{1}{2} a_1^2 \frac{1}{1-(a_1^2+a_2)/2}.$$ The second term yields $$ - \frac{1}{2} a_2 + \frac{1}{2} a_2 \frac{1}{1-(a_2^2+a_4)/2} + \frac{1}{4} a_2 (a_1^2+a_2) \frac{1}{1-(a_2^2+a_4)/2}.$$

This finally yields the equation for the centipede operator $$\sum_{n\ge 1} Z(Q_n) = -\frac{1}{2} (a_1^2 + a_2) + \frac{\frac{1}{2} a_1^2}{1-(a_1^2+a_2)/2} + \frac{\frac{1}{2} a_2 + \frac{1}{4}a_2 (a_1^2+a_2)}{1-(a_2^2+a_4)/2}.$$

We can now substitute into this operator to obtain various generating functions. The repertoire for the bushels always contains a $z$ term as it goes into the slot to represent the node to which the leaves are attached.

The first is $$\sum_{n\ge 1} Z(Q_n)(z) = \frac{z^4}{1-z^2}.$$

This simply represents the fact that there is one centipede when there are no leaves (we are not counting the $n+1$ nodes on the horizontal axis/spine of the centipede since no bushels are being attached there).

Now suppose there is at most one leaf at the outer nodes. This yields $$\sum_{n\ge 1} Z(Q_n)(z+z^2) = -{\frac {{z}^{4} \left( {z}^{2}+z+1 \right) \left( {z}^{7}+{z}^{5}-{ z}^{4}+2\,{z}^{3}-1 \right) }{ \left( {z}^{6}+{z}^{2}-1 \right) \left( {z}^{3}+z-1 \right) }}.$$

Finally consider that there may be any number of leaves. This gives $$\sum_{n\ge 1} Z(Q_n)\left(\frac{z}{1-z}\right) = {\frac {{z}^{4} \left( {z}^{6}+{z}^{5}-2\,{z}^{4}-{z}^{3}-{z}^{2}+1 \right) }{ \left( -1+z \right) ^{2} \left( z+1 \right) \left( {z}^{ 6}-2\,{z}^{4}-{z}^{2}+1 \right) \left( {z}^{3}-2\,{z}^{2}-z+1 \right) }}.$$

As pointed out earlier these last two do not yet have OEIS entries. They are $$0, 0, 0, 1, 2, 4, 4, 7, 8, 14, 17, 28, 36, 57, 76, 118, 162, 247, 346, 521,\ldots$$ and $$0, 0, 0, 1, 2, 6, 10, 22, 37, 73, 124, 233, 404, 743, 1306, 2377, 4221, 7645,\ldots$$

Here is some Maple code that can be used to explore these sequences and the corresponding cycle indices.

with(combinat):

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;

cp_perm_T :=
proc(n)
    if n=0 then return 1 fi;
    if n=1 then return 1/2*(a[1]^2+a[2]) fi;

    1/4*(a[1]^4+2*a[1]^2*a[2]+a[2]^2)*cp_perm_T(n-2);
end;

cp_perm_T_ex :=
proc(n)
    1/2^n*(a[1]^2+a[2])^n;
end;


cp_perm_S :=
proc(n)
    if n=0 then return 1 fi;
    if n=1 then return 1/2*(a[1]^2+a[2]) fi;

    1/4*(2*a[2]^2+2*a[4])*cp_perm_S(n-2);
end;

cp_perm_S_ex :=
proc(n)
    local m;

    m := floor(n/2);

    if type(n, even) then
        1/2^m*(a[2]^2+a[4])^m
    else
        1/2^(m+1)*(a[1]^2+a[2])*(a[2]^2+a[4])^m;
    fi;
end;

cp :=
proc(n)
    option remember;

    expand(1/2*a[1]^2*cp_perm_T(n)+1/2*a[2]*cp_perm_S(n));
end;



cp_gf :=
proc(lv, n)
    option remember;
    local m, gf;

    gf := 0;
    for m to 2*n do
        gf := gf + pet_varinto_cind(lv, cp(m));
    od;

    seq(coeftayl(series(gf, z=0, 2*n+1), z=0, m), m=1..2*n);
end;

cp_gf_closed :=
proc(lv)
    local cind_op;

    cind_op := -1/2*(a[1]^2+a[2]) +
    1/2*a[1]^2/(1-(a[1]^2+a[2])/2) +
    (1/2*a[2] + 1/4*a[2]*(a[1]^2+a[2]))/(1-(a[2]^2+a[4])/2);

    factor(pet_varinto_cind(lv, cind_op));
end;


This MSElink enumerates caterpillars up to isomorphism, which is sort of related.

Addendum. The single $4$-cycle also has a special rotational symmetry that brings the upper and lower slots into the same orbit as the left and right end point. This symmetry is not being considered here. It is not difficult to subtract the term for $Z(Q_1)$ that we have calculated and replace it by $Z(D_4).$

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