Forbidden pairs for kk-connected Hamiltonian graphs

For an integer kk with k≥2k≥2 and a pair of connected graphs F1F1 and F2F2 of order at least three, we say that {F1,F2}{F1,F2} is a kk-forbidden pair if every kk-connected {F1,F2}{F1,F2}-free graph, except possibly for a finite number of exceptions, is Hamiltonian. If no exception arises, {F1,F2}{F1,F2} is said to be a strong kk-forbidden pair. The 2-forbidden pairs and the strong 2-forbidden pairs are determined by Faudree and Gould (1997) [11] and Bedrossian (1991) [1], respectively. All of them contain K1,3K1,3. In this paper, we prove that {K1,k+1,P4}{K1,k+1,P4} is a strong kk-forbidden pair, which shows that K1,3K1,3 is not always necessary in a kk-forbidden pair for k≥3k≥3. On the other hand, we prove that each kk-forbidden pair contains K1,lK1,l for some l≤k+1l≤k+1. We also discuss several other Hamiltonian properties of kk-connected {K1,k+1,P4}{K1,k+1,P4}-free graphs.