Premium
On circuits and pancyclic line graphs
Author(s) -
Benhocine A.,
Clark L.,
Köhler N.,
Veldman H. J.
Publication year - 1986
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/jgt.3190100317
Subject(s) - combinatorics , mathematics , graph , vertex (graph theory) , hamiltonian path , upper and lower bounds , connectivity , hamiltonian (control theory) , bound graph , discrete mathematics , line graph , graph power , mathematical analysis , mathematical optimization
Clark proved that L ( G ) is hamiltonian if G is a connected graph of order n ≥ 6 such that deg u + deg v ≥ n – 1 – p ( n ) for every edge uv of G , where p ( n ) = 0 if n is even and p ( n ) = 1 if n is odd. Here it is shown that the bound n – 1 – p ( n ) can be decreased to (2 n + 1)/3 if every bridge of G is incident with a vertex of degree 1, which is a necessary condition for hamiltonicity of L ( G ). Moreover, the conclusion that L ( G ) is hamiltonian can be strengthened to the conclusion that L ( G ) is pancyclic. Lesniak‐Foster and Williamson proved that G contains a spanning closed trail if | V ( G )| = n ≥ 6, δ( G ) ≥ 2 and deg u + deg v ≥ n – 1 for every pair of nonadjacent vertices u and v . The bound n – 1 can be decreased to (2 n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.