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)?

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.