Degree Sum Conditions for Traceable Quasi-Claw-Free Graphs

Abstract:

      A traceable graph is a graph containing a Hamilton path. Let $N[v]=N(v)\cup\{v\}$ and $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$. A graph $G$ is called quasi-claw-free if $J(u,v)\neq \emptyset$ for any $u,v\in V(G)$ with distance of two. Let $\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$ is an independent set of $V(G)$ with $|S|=k\},$ where $d(v)$ denotes the degree of $v$ in $G$. In this paper, we prove that if $G$ is a connected quasi-claw-free graph of order $n$ and $\sigma_{3}(G)\geq {n-2}$, then $G$ is traceable; moreover, we give an example to show the bound in our result is best possible. We obtain that if $G$ is a connected quasi-claw-free graph of order $n$ and $\sigma_{2}(G)\geq \frac{2({n-2})}{3}$, then $G$ is traceable.