TY - JOUR
T1 - An s-hamiltonian line graph problem
AU - Chen, Zhi Hong
AU - Lai, Hong Jian
AU - Shiu, Wai Chee
AU - Li, Deying
N1 - D. Li was supported in part by the National Science Foundation of China (10671208) and Key Labs of Data Engineering and Knowledge Engineering, MOE.
PY - 2007/6
Y1 - 2007/6
N2 - 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}.
AB - 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}.
UR - http://www.scopus.com/inward/record.url?scp=34547249218&partnerID=8YFLogxK
U2 - 10.1007/s00373-007-0727-y
DO - 10.1007/s00373-007-0727-y
M3 - Journal article
AN - SCOPUS:34547249218
SN - 0911-0119
VL - 23
SP - 241
EP - 248
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 3
ER -