Generation of Cycle Permutation Graphs and Permutation Snarks
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913097617244160 |
|---|---|
| author | Goedgebeur, Jan Renders, Jarne Van Overberghe, Steven |
| author_facet | Goedgebeur, Jan Renders, Jarne Van Overberghe, Steven |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12606 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generation of Cycle Permutation Graphs and Permutation Snarks Goedgebeur, Jan Renders, Jarne Van Overberghe, Steven Combinatorics Discrete Mathematics 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. |
| title | Generation of Cycle Permutation Graphs and Permutation Snarks |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2411.12606 |