半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)cup{v}$, $J(u,v)={win N(u)cap N(v):N(w)subseteq N[u]cup N[v]}$.若图中任意距离为2的两点$u,v$满足$J(u,v)neq emptyset$,则称该图为半无爪图.令$sigma_{k}(G)=min{sum_{vin S}d(v):S$为$G$中含有$k$个点的独立集},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$sigma_{3}(G)geq {n-2}$,则图$G$为可迹图; 文中给出一个图例，说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$sigma_{2}(G)geq frac{2({n-2})}{3}$,则该图为可迹图.

Degree Sum Conditions for Traceable Quasi-Claw-Free Graphs

A traceable graph is a graph containing a Hamilton path. Let $N[v]=N(v)cup{v}$ and $J(u,v)={win 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,vin V(G)$ with distance of two. Let $sigma_{k}(G)=min{sum_{vin 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.