Relationships between the length of a longest path and the relative length
Shuya Chiba, Ryota Matsubara, Masao Tsugaki · 2010
Let G be a graph, and let p(G )a ndc(G) be the order of a longest path and a longest cycle of G, respectively. In [J. Graph Theory 30 (1999), 91– 99], Saito proved that if G is a 2-connected graph with p(G) − c(G) ≥ 2, then p(G) ≥ σ3(G) − 1. In this paper, we evaluate the length of a longest path of G by using σ4(G). Specifically, our main results are the following. (i) If G is a 3-connected graph with p(G) − c(G) ≥ 3, then p(G) ≥ σ4(G)−5, and (ii) if G is a 3-connected graph with p(G)−c(G) ≥ 2, then p(G) ≥ 3σ4(G)/4 − 1. The statement (ii) is a generalization of Saito’s theorem for 3-connected graphs. In fact, we characterize all graphs G with p(G) − c(G) ≥ 2a ndp(G )=3 σ4(G)/4 − 1. Following these results, we propose a conjecture, and obtain an application for the problem concerning the existence of vertex-disjoint paths.