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\le k\le 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$. Corrigendum added March 19, 2018.
@article{10_37236_3969,
author = {Robert Luko\v{t}ka and Edita M\'a\v{c}ajov\'a and J\'an Maz\'ak and Martin \v{S}koviera},
title = {Small snarks with large oddness},
journal = {The electronic journal of combinatorics},
year = {2015},
volume = {22},
number = {1},
doi = {10.37236/3969},
zbl = {1308.05051},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3969/}
}
TY - JOUR
AU - Robert Lukoťka
AU - Edita Máčajová
AU - Ján Mazák
AU - Martin Škoviera
TI - Small snarks with large oddness
JO - The electronic journal of combinatorics
PY - 2015
VL - 22
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3969/
DO - 10.37236/3969
ID - 10_37236_3969
ER -
%0 Journal Article
%A Robert Lukoťka
%A Edita Máčajová
%A Ján Mazák
%A Martin Škoviera
%T Small snarks with large oddness
%J The electronic journal of combinatorics
%D 2015
%V 22
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3969/
%R 10.37236/3969
%F 10_37236_3969
Robert Lukoťka; Edita Máčajová; Ján Mazák; Martin Škoviera. Small snarks with large oddness. The electronic journal of combinatorics, Tome 22 (2015) no. 1. doi: 10.37236/3969
