An s-hamiltonian line graph problem

Zhi Hong Chen*, Hong Jian Lai, Wai Chee SHIU, Deying Li

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)


For an integer k > 0, a graph G is k-triangular if every edge of G lies in at least k distinct 3-cycles of G. In (J Graph Theory 11:399-407 (1987)), Broersma and Veldman proposed an open problem: for a given positive integer k, determine the value s for which the statement "Let G be a k-triangular graph. Then L(G), the line graph of G, is s-hamiltonian if and only L(G) is (s + 2)-connected" is valid. Broersma and Veldman proved in 1987 that the statement above holds for 0 ≤ s ≤ k and asked, specifically, if the statement holds when s = 2k. In this paper, we prove that the statement above holds for 0 ≤ s ≤ max{2k, 6k - 16}.

Original languageEnglish
Pages (from-to)241-248
Number of pages8
JournalGraphs and Combinatorics
Issue number3
Publication statusPublished - Jun 2007

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'An s-hamiltonian line graph problem'. Together they form a unique fingerprint.

Cite this