Small snarks with large oddness (Q2260625)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Small snarks with large oddness |
scientific article |
Statements
Small snarks with large oddness (English)
0 references
11 March 2015
0 references
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.
0 references
cubic graph
0 references
snark
0 references
oddness
0 references
resistance
0 references