A note on maximal nonhamiltonian Burkard-Hammer graphs (Q873804)

A Burkard-Hammer graph is a graph \(G=(V,E)\) which enables to split its vertex set \(V\) into two sets \(I\) and \(K\) such that \(| I| <| K| \) and the induced subgraphs \(G[I]\) and \(G[K]\) are edgeless and complete, respectively. Moreover, \(G\) is called a maximal nonhamiltonian if \(G\) is nonhamiltonian but \(G+uv\) is hamiltonian for every \(uv\notin E\) where \(u\in I\) and \(v\in K\). In this paper answers are given to questions raised by \textit{Ngo Dac Tan} and \textit{C. Iamjaroen} [J. Discrete Math. Sci. Cryptography 9, 235--252 (2006; Zbl 1103.05046)] concerning the existence of certain vertices in such graphs.