Premium
Long paths, long cycles, and their relative length
Author(s) -
Saito Akira
Publication year - 1999
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199902)30:2<91::aid-jgt3>3.0.co;2-8
Subject(s) - combinatorics , mathematics , bound graph , graph , upper and lower bounds , discrete mathematics , graph power , line graph , mathematical analysis
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{deg G x + deg G y + deg G 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