An s-Hamiltonian Line Graph Problem

Zhi-Hong Chen, Butler University

Abstract

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 = 2 k. In this paper, we prove that the statement above holds for 0 ≤ s ≤ max{2 k, 6 k − 16}.

Note: Link is to the article in a subscription database available to users affiliated with Butler University. Appropriate login information will be required for access. Users not affiliated with Butler University should contact their local librarian for assistance in locating a copy of this article.