Generation of Cycle Permutation Graphs and Permutation Snarks
For graph theorists studying cubic graphs, snarks, and hamiltonicity, this work provides computational advances and resolves an open problem, though the results are domain-specific and incremental in nature.
The paper presents an algorithm for generating all non-isomorphic cycle permutation graphs and permutation snarks up to orders 34 and 46 respectively, improving previous computational bounds. It provides new lower bounds for certain permutation snarks, completes the characterization of orders for which non-hamiltonian cycle permutation graphs exist (answering a 1972 question by Klee), and yields counterexamples to conjectures by Jackson and Zhang.
We present an algorithm for the efficient generation of all pairwise non-isomorphic cycle permutation graphs, i.e. cubic graphs with a $2$-factor consisting of two chordless cycles, non-hamiltonian cycle permutation graphs and permutation snarks, i.e. cycle permutation graphs that do not admit a $3$-edge-colouring. This allows us to generate all cycle permutation graphs up to order $34$ and all permutation snarks up to order $46$, improving upon previous computational results by Brinkmann et al. Moreover, we give several improved lower bounds for interesting permutation snarks, such as for a smallest permutation snark of order $6 \bmod 8$ or a smallest permutation snark of girth at least $6$ and give more evidence in support of a conjecture of Goddyn. These computational results also allow us to complete a characterisation of the orders for which non-hamiltonian cycle permutation graphs exist, answering an open question by Klee from 1972, and yield many more counterexamples to conjectures by Jackson and Zhang.