Hamilton-connected properties of 3-connected {claw, hourglass, bull}-free graphs

Panpan Wang1,2, Liming Xiong3
1School of Mathematics and Statistics, Beijing Institute of Technology, Beijing 100081, P.R. of China
2School of Mathematics and Statistics, Weifang University, Weifang, 261061, P.R. of China
3School of Mathematics and Statistics, Beijing Key Laboratory on MCAACI, Beijing Institute of Technology, Beijing 100081, P.R. of China

Abstract

An hourglass \(\Gamma_0\) is the graph with degree sequence \(\{4,2,2,2,2\}\). In this paper, for integers \(j\geq i\geq 1\), the bull \(B_{i,j}\) is the graph obtained by attaching endvertices of two disjoint paths of lengths \(i,j\) to two vertices of a triangle. We show that every 3-connected \(\{K_{1,3},\Gamma_0,X\}\)-free graph, where \(X\in \{ B_{2,12},\,B_{4,10},\,B_{6,8}\}\), is Hamilton-connected. Moreover, we give an example to show the sharpness of our result, and complete the characterization of forbidden induced bulls implying Hamilton-connectedness of a 3-connected {claw, hourglass, bull}-free graph.

Keywords: Hamilton-connected, Forbidden subgraph, Claw, Hourglass, Bull