Small snarks with large oddness (Q2260625)

Summary: We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph \(G\) with oddness \(\omega(G)\) other than the Petersen graph has at least \(5.41\, \omega(G)\) vertices, and for each integer \(k\) with \(2\leq k\leq 6\) we construct an infinite family of cubic graphs with cyclic connectivity \(k\) and small oddness ratio \(|V(G)|/\omega(G)\). In particular, for cyclic connectivity 2, 4, 5, and 6 we improve the upper bounds on the oddness ratio of snarks to 7.5, 13, 25, and 99 from the known values 9, 15, 76, and 118, respectively. In addition, we construct a cyclically 4-connected snark of girth 5 with oddness 4 on 44 vertices, improving the best previous value of 46.