Long paths, long cycles, and their relative length
Akira Saito · Journal of Graph Theory · 1999
Let p(G) and c(G) be the order of a longest path and a longest cycle in a graph G, respectively. Let σ3(G) = min{degG x + degG y + degG z : {:x, y, z} is an independent set of vertices of G}. Extending the result by Enomoto et al. (J Graph Th 20 (1995), 213–225) on the difference p(G) − c(G), we prove that a 2-connected graph G of order n satisfies (1) p(G) − c(G) ≤ 1 or p(G) ≥ σ3(G) − 1, and (2) if σ3(G) ≤ n, then p(G) − c(G) ≤ n − σ3(G) + 1 or p(G) ≥ σ3(G). Then, using the above result, we give a new lower bound for p(G). This bound corresponds to the bound on c(G) given by Bauer et al. (Discrete Math 79 (1989/90), 59–70). © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 91–99, 1999