 Degree Sum Conditions for Traceable Quasi-Claw-Free Graphs
Received:March 07, 2021  Revised:June 26, 2021
Key Word: traceable graph   quasi-claw-free graphs   degree sum
Fund ProjectL:Supported by the National Natural Science Foundation of China (Grant No.\,11901268) and the Ph.D Research Startup Foundation of Liaoning Normal University (Grant No.2021BSL011).
 Author Name Affiliation Shuaijun CHEN College of Science, Liaoning University of Technology, Liaoning 121001, P. R. China Xiaodong CHEN School of Mathematics, Liaoning Normal University, Liaoning 116029, P. R. China Mingchu LI School of Software, Dalian University of Technology, Liaoning 116620, P. R. China
Hits: 132
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.