On the Burkard-Hammer condition for hamiltonian split graphs

A graph G = (V, E) is called a split graph if there exists a partition V = I boolean OR K such that the subgraphs of G induced by I and K are empty and complete graphs, respectively. In 1980, Burkard and Hammer gave a necessary but not sufficient condition for hamiltonian split graphs with vertical bar I vertical bar < vertical bar K vertical bar. In this paper, we show that the Burkard-Hammer condition is also sufficient for the existence of a Hamilton cycle in a split graph G such that 5 not equal vertical bar I vertical bar < vertical bar K vertical bar and the minimum degree delta(G) >= vertical bar I vertical bar - 3. For the case 5 = vertical bar I vertical bar < vertical bar K vertical bar, all split graphs satisfying the Burkard-Hammer condition but having no Hamilton cycles are also described. (c) 2005 Elsevier B.V. All rights reserved.