Permutation snarks of order 2 (mod 8)

Abstract

A permutation snark is a cubic graph which has a 2-factor consisting oftwo chordless cycles and is not 3-edge-colourable. Every permutation snark is cyclically4-edge-connected, has girth at least 5, and its order is twice an odd number.Employing exhaustive computer search, Brinkmann et al. (2013) discovered a cyclically5-edge-connected permutation snark of order 34, disproving a conjecture ofC.-Q. Zhang (1997) that the Petersen graph is the only such graph. Hagglund andHomann-Ostenhof (2017) extended this example to an innite series of cyclically5-edge-connected permutation snarks of order n = 24k + 10 for every positive integerk. Here we present three general methods of constructing permutation snarksand with their help provide permutation snarks with cyclic connectivity 4 and 5 forevery possible order 2 (mod 8).