Cubic Graphs with Large Circumference Deficit
Edita Máčajová, Ján Mazák · Journal of Graph Theory · 2015
The circumference of a graph G is the length of a longest cycle. By exploiting our recent results on resistance of snarks, we construct infinite classes of cyclically 4-, 5-, and 6-edge-connected cubic graphs with circumference ratio bounded from above by 0.876, 0.960, and 0.990, respectively. In contrast, the dominating cycle conjecture implies that the circumference ratio of a cyclically 4-edge-connected cubic graph is at least 0.75. Up to our knowledge, no upper bounds on this ratio have been known before for cubic graphs with cyclic edge-connectivity above 3. In addition, we construct snarks with large girth and large circumference deficit, solving Problem 1 proposed in [J. Hägglund and K. Markström, On stable cycles and cycle double covers of graphs with large circumference, Disc Math 312 (2012), 2540–2544].