Relative length of longest paths and cycles in 3‐connected graphs
Rao Li, Akira Saito, RICHARD H. SCHELP · Journal of Graph Theory · 2001
Abstract For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that $\textstyle{\sum^{4}_{i=1}\,{\rm deg}_{G}\,x_{i} \ge {3\over2}\,n + 1}$ for every independent set {x1, x2, x3, x4}, then G satisfies c(G) ≥ p(G) − 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001