On circuits and pancyclic line graphs


Benhocine, A. and Clark, L. and Köhler, N. and Veldman, H.J. (1986) On circuits and pancyclic line graphs. Journal of Graph Theory, 10 (3). pp. 411-425. ISSN 0364-9024

open access
Abstract: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 (2n + 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 (2n + 3)/3 if G is connected and bridgeless, which is necessary for G to have a spanning closed trail.
Item Type:Article
Copyright:© 1986 Wiley InterScience
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/70813
Official URL:https://doi.org/10.1002/jgt.3190100317
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page