Authors: T. Tian, L. Xiong Title: 2-connected Hamiltonian claw-free graphs involving degree sum of adjacent vertices Source: Discussiones Mathematicae Graph Theory Received 19.05.2017, Revised 06.02.2018, Accepted 06.02.2018, doi: 10.7151/dmgt.2125 | |
Abstract: For a graph H, define {{`σ}_{2}}(H)=\min{ d(u)+d(v)| uv ∈E(H)}. Let H be a 2-connected claw-free simple graph of order n with δ(H)≥ 3. In [J. Graph Theory 86 (2017) 193--212], Chen proved that if {{`σ }_{2}}(H)≥\frac{n}{2}-1 and n is sufficiently large, then H is Hamiltonian with two families of exceptions. In this paper, we refine the result. We focus on the condition {{`σ}_{2}}(H)≥ \frac{2n}{5}-1, and characterize non-Hamiltonian 2-connected claw-free graphs H of order n sufficiently large with {{`σ }_{2}}(H)≥ \frac{2n}{5}-1. As byproducts, we prove that there are exactly six graphs in the family of 2-edge-connected triangle-free graphs of order at most seven that have no spanning closed trail and give an improvement of a result of Veldman in [Discrete Math. 124 (1994) 229--239]. | |
Keywords: Hamiltonian cycle, degree sum, dominating closed trail, closure | |
Links: |