2013/10/03 by Máčajová, Edita, Mazák, Ján
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1310.1042
The circumference c(G) 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 c(G)/|V(G)| 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. 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].