A classfication for maximal nonhamiltonian Burkard-Hammer graphs

A graph G = (V, E) is called a split graph if there exists a partition V = I ∪K such that the subgraphs G[I ] and G[K] of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary condition for a split graph G with |I | < |K| to be hamiltonian. We will call a split graph G with |I | < |K| satisfying this condition a Burkard-Hammer graph. Further, a split graph G is called a maximal nonhamiltonian split graph if G is nonhamiltonian but G + uv is hamiltonian for every uv 6∈ E where u ∈ I and v ∈ K. Recently, Ngo Dac Tan and Le Xuan Hung have classified maximal nonhamiltonian Burkard-Hammer graphs G with minimum degree δ(G) ≥ |I | − 3. In this paper, we classify maximal nonhamiltonian Burkard-Hammer graphs G with |I | 6= 6, 7 and δ(G) = |I | − 4.