
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

