
Vietnam Journal of Mathematics 34:4(2006)
397409

Note on Maximal Nonhamiltonian
BurkardHammer Graphs

Ngo Dac Tan

Abstract. 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 E
where u ∈ I and v ∈ K.
In a nearlier work, the author and Iamjaroen have asked whether every
maximal nonhamiltonian Burkard – Hammer graph G with the minimum degree
δ(G) ≥ I  k where k
≥ 3 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 4 and to the second question for all k 5.

2000 Mathematics Subject Classification: 05C45.

Keywords: Split graph, BurkardHammer condition,
BurkardHammer graph, hamiltonian graph, maximal nonhamiltonian split
graph.


Established
by Vietnam Academy of Science and Technology & Vietnam Mathematical
Society
Published
by Springer since January 2013

