Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset $${S\subseteq V}$$ , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by $${d(x, H)=\min\{d(x,y)\ |\ y\in V(H)\}}$$ , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all $${x\in V(G)}$$ . An induced path P of G is said to be maximal if there is no induced path P′ satisfying $${V(P)\subset V(P')}$$ and $${V(P')\setminus V(P)\neq \emptyset}$$ . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds: $$ d(u)+d(v)\geq |V(G)|-p+2. $$ Under this assumption, we prove that G has a 2-dominating induced cycle and G is Hamiltonian. Copyright Springer-Verlag 2009