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

摘要

Let G = (V, E) be a connected graph. For a vertex subset ${Ssubseteq 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) | yin 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 ${xin 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.