کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4646890 | 1632410 | 2014 | 8 صفحه PDF | دانلود رایگان |
A graph HH has the hourglass property if in every induced hourglass SS (the unique simple graph with the degree sequence (4, 2, 2, 2, 2)), there are two non-adjacent vertices which have a common neighbor in H−V(S)H−V(S). Let GG be a claw-free simple graph and kk a positive integer. In this paper, we prove that if either GG is hourglass-free or GG has the hourglass property and δ(G)≥4δ(G)≥4, then GG has a 2-factor with at most kk components if and only if it has an even factor with at most kk components. We provide some of its applications: combining the result (the case when k=1k=1) with Jaeger (1979) and Chen et al. (2006), we obtain that every 4-edge-connected claw-free graph with the hourglass property is hamiltonian and that every essentially 4-edge-connected claw-free hourglass-free graph of minimum degree at least three is hamiltonian, thereby generalizing the main result in Kaiser et al. (2005) and the result in Broersma et al. (2001) respectively in which the conditions on the vertex-connectivity are replaced by the condition of (essential) 4-edge-connectivity. Combining our result with Catlin and Lai (1990), Lai et al. (2010) and Paulraja (1987), we also obtain several other results on the existence of a hamiltonian cycle in claw-free graphs in this paper.
Journal: Discrete Mathematics - Volume 332, 6 October 2014, Pages 15–22