Circumference of 3-connected cubic graphs

DOI10.1016/J.JCTB.2017.08.008MaRDI QIDQ1682212zbMATH OpenOpenAlexFDO

Authors Qinghai Liu, Xingxing Yu, Zhao Zhang

Publication date 28 November 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1708.08865

zbMATH Keywords

circumferencecubic graphcycle

Mathematics Subject Classification ID

Paths and cycles (05C38) Connectivity (05C40)

Abstract: The circumference of a graph is the length of its longest cycles. Jackson established a conjecture of Bondy by showing that the circumference of a 3-connected cubic graph of order $n$ is $Omega(n^{0.694})$. Bilinski {it et al.} improved this lower bound to $Omega(n^{0.753})$ by studying large Eulerian subgraphs in 3-edge-connected graphs. In this paper, we further improve this lower bound to $Omega(n^{0.8})$. This is done by considering certain 2-connected cubic graphs, finding cycles through two given edges, and distinguishing the cases whether or not these edges are adjacent.

Recommendations

• On the circumference of 3-connected cubic triangle-free plane graphs
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Cubic graphs with large circumference deficit
• scientific article; zbMATH DE number 3906529
• On the circumference of 3-connected graphs

Cites work

• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Cycles containing 12 vertices in 3-connected cubic graphs
• Cycles through 23 vertices in 3-connected cubic planar graphs
• Cycles through five edges in 3-connected cubic graphs
• Cycles through four edges in 3-connected cubic graphs
• Longest Cycles in 3-Connected 3-Regular Graphs
• Longest cycles in 3-connected cubic graphs
• On Hamiltonian Circuits
• Trees in Polyhedral Graphs

Cited in

(15)

• On the circumferences of regular 2-connected graphs
• Shortness coefficient of cyclically 4-edge-connected cubic graphs
• On the circumference of 3-connected cubic triangle-free plane graphs
• Dual circumference and collinear sets
• The diameter of the cube-connected cycles
• Cubic graphs with large circumference deficit
• scientific article; zbMATH DE number 3906529 (Why is no real title available?)
• scientific article; zbMATH DE number 4057538 (Why is no real title available?)
• Longest cycles in cyclically 4-edge-connected cubic planar graphs
• Dual circumference and collinear sets
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Length of cycles in generalized Petersen graphs
• Small hitting sets for longest paths and cycles
• Edge decomposition of connected claw-free cubic graphs
• A note on 3-connected cubic planar graphs

This page was built for publication: Circumference of 3-connected cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1682212)