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. 411425. ISSN 03649024

PDF
646kB 
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. LesniakFoster 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 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/70813 
Official URL:  http://dx.doi.org/10.1002/jgt.3190100317 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page