Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs

摘要

The circumference of a graph is the length of its longest cycles. Results of Jackson, and Jackson and Wormald, imply that the circumference of a 3-connected cubic n-vertex graph is Omega(n(0.694)), and the circumference of a 3-connected claw-free graph is Omega(n(0.121)). We generalize and improve the first result by showing that every 3-edge-connected graph with m edges has an Eulerian subgraph with Omega(m(0.753)) edges. We use this result together with the Ryjacek closure operation to improve the lower bound on the circumference of a 3-connected claw-free graph to Omega(n(0.753)). Our proofs imply polynomial time algorithms for finding large Eulerian subgraphs of 3-edge-connected graphs and long cycles in 3-connected claw-free graphs.