Homogeneous Traceability In Claw-Free Graphs

Abstract

A graph $G$ is homogeneously traceable if for each vertex $v$ of $G$ there exists a hamiltonian path in $G$ with initial vertex $v$. A graph is called claw-free if it has no induced $K_3$ as a subgraph.

In this paper, we prove that if $G$ is a $k$-connected ($k>1$) claw-free graph of order $n$ such that the sum of degrees of any $k+2$ independent vertices is at least $n-k$, then $G$ is homogeneously traceable. For $k=2$, the bound $n-k$ is best possible.

As a corollary we obtain that if $G$ is a $2$-connected claw-free graph of order $n$ such that $NC(G)\ge (n-3)/2$, where $NC(G)=min\{|N(u)\cup N(v)|:uv\notin E(G)\}$, then $G$ is homogeneously traceable. Moreover, the bound $(n-3)/2$ is best possible.