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:
PDF