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