Degree sums and subpancyclicity in line graphs

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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
53 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
  • IR-74722
  • Degree sum
  • METIS-206788

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

  • Cite this