The Local Structure of Claw-Free Graphs Without Induced Generalized Bulls

In this paper, we show the following: Let G be a connected claw-free graph such that G has a connected induced subgraph H that has a pair of vertices { v₁, v₂} of degree one in H whose distance is d+ 2 in H. Then H has an induced subgraph F, which is isomorphic to B_{i , j}, with { v₁, v₂} ⊆ V(F) and i+ j= d+ 1 , with a well-defined exception. Here B_{i , j} denotes the graph obtained by attaching two vertex-disjoint paths of lengths i, j≥ 1 to a triangle. We also use the result above to strengthen the results in Xiong et al. (Discrete Math 313:784–795, 2013) in two cases, when i+ j≤ 9 , and when the graph is Γ -free. Here Γ is the simple graph with degree sequence 4, 2, 2, 2, 2. Let i, j> 0 be integers such that i+ j≤ 9. Thenevery 3-connected { K_{1 , 3}, B_{i , j}} -free graph G is hamiltonian, andevery 3-connected { K_{1 , 3}, Γ , B_{2 i , 2 j}} -free graph G is hamiltonian. The two results above are all sharp in the sense that the condition “i+ j≤ 9 ” couldn’t be replaced by ` ` i+ j≤ 10 ”.