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 NameAffiliation
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
Download times: 153
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.
Citation:
DOI:10.3770/j.issn:2095-2651.2022.02.003
View Full Text  View/Add Comment  Download reader