Degree sums and subpancyclicity in line graphs

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

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
64 Downloads (Pure)

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 - 2002

Keywords

  • Line graph
  • Path
  • Subpancyclicity
  • Degree sum

Fingerprint

Dive into the research topics of 'Degree sums and subpancyclicity in line graphs'. Together they form a unique fingerprint.

Cite this