Back to University of Twente portal
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
![[img]](http://doc.utwente.nl/style/images/fileicons/application_pdf.png)
| PDF 631Kb |
| 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 |
| 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 |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page