4
$\begingroup$

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is of type $\pi$, or that $\pi$ is realized by $G$. Most constructions in the previous thread are based on the Petersen graph, which is of type $(5,5)$. All those constructions are either of type $(n)$ or of type $(a,b)$ with $a,b$ odd and at least one $\equiv1\pmod4$.

Since then, I have managed to realize a partition with more than two parts, namely $(12,5,5)$, by the following construction using two $K_{3,3}$'s.
enter image description here Each 2-factor must contain exactly two edges of $a,b,c$ and two of $a',b',c'$. But the two $K_{3,3}$-like graphs don't have Hamilton paths between two of the blue incoming edges, so the 2-factor must contain on either side a smaller cycle, thus a $C_5$ (coming from a $C_4$ of the $K_{3,3}$).
Note that this graph is not hypo-Hamiltonian w.r.t. any of the four middle vertices, so those can be replaced by certain other graphs, yielding a bunch of realizable partitions $(k,5,5)$, but also $(k,5,5,...,5)$ by iterating, for certain $k$'s.

So far so good, but all the non Hamiltonian graphs so far have odd cycles in their 2-factors.

Now I just found that the Coxeter graph is a realization of the type $(14,14)$, as shown here. The picture displays the Coxeter graph in "distance-transitive format"; the red edges, including c4-c5, d2-d7, e3-e6, define a 1-factor, the green and blue ones the cycles of a 2-factor.
enter image description here

Performing similar constructions as in the previous thread, we can obtain from this several graphs of other 'even' types like $(18,14)$, $(24,14)$ or $(70,70)$. But as far as I see, this cannot yield types $(4a,4b)$ or $(4a+3,4b+3)$, nor types with three or more even cycle lengths.

  • Can some partitions of types $(4a,4b)$ or $(4a+3,4b+3)$ or $(2a,2b,2c)$ also be realized?

The next question arises naturally from the fact that the numbers 5 (Petersen) and 14 (Coxeter) are the Catalan numbers $\mathcal C_3$ and $\mathcal C_4$:

  • Is there an infinite family of graphs realizing $(\mathcal C_k,\mathcal C_k)$?

I don't think such graphs would be vertex-transitive for $k\geqslant 5$, because according to p.55 of this article, Kutnar and Marusic [28] proved that with exception of the Coxeter graph, all connected vertex transitive graphs of order 4p are Hamiltonian. Also, there are only five non-Hamilton vertex transitive graphs known at all.

On the other hand, graphs realizing $(\mathcal C_k,\mathcal C_k)$ should have a fairly high degree of symmetry (intuitively, higher than for graphs of type $(a,b)$ with $a\ne b$).

Given that the Coxeter graph has a 7-fold symmetry (as does also the Heawood graph, which is of type $(14)$), a broader question would be:

  • Is there a partition that can be realized by a graph with $k$-fold symmetry for a $k\geqslant 8$ (prime or not)?
$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.