Abstract
A graph is called subpancyclic if it contains a cycle of length k for each k between 3 and the circumference of the graph. In this paper, we show that if the degree sum of the vertices along each 2-path of a graph G exceeds (n + 6)/2, or if the degree sum of the vertices along each 3-path of G exceeds (2n + 16)/3, then its line graph L(G) is subpancyclic. Simple examples show that these bounds are best possible. Our results shed some light on the content of a famous Metaconjecture of Bondy.
Original language | English |
---|---|
Pages (from-to) | 255-267 |
Number of pages | 13 |
Journal | Discrete Mathematics |
Volume | 242 |
Issue number | 1-3 |
DOIs | |
Publication status | Published - 1 Jun 2002 |
Externally published | Yes |
Keywords
- Degree sum
- Line graph
- Path
- Subpancyclicity
Fingerprint
Dive into the research topics of 'Degree sums and subpancyclicity in line graphs'. Together they form a unique fingerprint.Cite this
Xiong, L., Broersma, H. J., Hoede, C., & Li, X. (2002). Degree sums and subpancyclicity in line graphs. Discrete Mathematics, 242(1-3), 255-267. https://doi.org/10.1016/S0012-365X(00)00468-4