Degree sums and subpancyclicity in line graphs

Liming Xiong, H. J. Broersma, C. Hoede, Xueliang Li

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
Plum Print visual indicator of research metrics
  • Citations
    • Citation Indexes: 2
  • Captures
    • Readers: 7
see details

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 languageEnglish
Pages (from-to)255-267
Number of pages13
JournalDiscrete Mathematics
Volume242
Issue number1-3
DOIs
Publication statusPublished - 1 Jun 2002
Externally publishedYes

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