1

Vietnam Journal of Mathematics 34:4(2006) 397-409

Note on Maximal Nonhamiltonian Burkard--Hammer Graphs

Ngo Dac Tan

Abstract. A graph $G=(V,E)$ is called a split graph if there exists a partition $V=I\cup 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\not\in E$ where $u\in I$ and $v\in K$. In an earlier work, the author and Iamjaroen have asked whether every maximal nonhamiltonian Burkard--Hammer graph $G$ with the minimum degree $\delta (G)\ge |I|-k$ where $k\ge 3$ possesses a vertex adjacent to all vertices of $G$ and whether every maximal nonhamiltonian Burkard--Hammer graph $G$ with $\delta (G)=|I|-k$ where $k>3$ and $|I|>k+2$ possesses a vertex with exactly $k-1$ neighbors in $I$. The first question and the second one have been proved earlier to have a positive answer for $k=3$ and $k=4$, respectively. In this paper, we give a negative answer both to the first question for all $k\ge 4$ and to the second question for all $k\ge 5$.

2000 Mathematics Subject Classification: 05C45.

Keywords: Split graph, Burkard--Hammer condition, Burkard--Hammer graph, hamiltonian graph, maximal nonhamiltonian split graph.