Degree sum conditions for traceable quasi-claw-free graphs
Received:March 07, 2021  Revised:June 09, 2021
Key Word: traceable graph   quasi-claw-free graphs   degree sum
Fund ProjectL:National Natural Science Foundation of China (Grant No.\,11901268)
 Author Name Affiliation Address Shuaijun Chen College of Science, Liaoning University of Technology 辽宁省锦州市古塔区士英街169号 Xiaodong Chen School of Mathematics, Liaoning Normal University Mingchu Li School of Softsware, Dalian University of Technology
Hits: 59
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 $d(u,v)=2$. Let $\sigma_{k}(G)=\min\{\sum_{v\in S}{\rm d}(v):S$ is an independent set of $V(G)$ with $|S|=k\}$. 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.