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 NameAffiliationAddress
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
Download times: 0
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 $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.
Citation:
DOI:
  View/Add Comment  Download reader