2012/12/14 by Robert Lukoťka, Lukotka, Robert, Edita Máčajová +5 · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.1212.3641
openalex publication_date 2012/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ω(G) other than the Petersen graph has at least 5.41⋅ω(G) vertices, and for each integer k with 2≤ k≤ 6 we construct an infinite family of cubic graphs with cyclic connectivity k and small oddness ratio |V(G)|/ω(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.