半无爪可迹图的度和条件

Degree Sum Conditions for Traceable Quasi-Claw-Free Graphs

中文关键词:  可迹图  半无爪图  度和

英文关键词:traceable graph  quasi-claw-free graphs  degree sum

中文摘要:

      可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in 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_{v\in 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}$,则该图为可迹图.

英文摘要:

      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.