Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: Description: VJM banner 

 

Home

 

Recent Issues

Volume 52

1

 

 

 

Volume 51

1

2

3

4

Volume 50

1

2

3

4

Volume 49

1

2

3

4

Volume 48

1

2

3

4

Past Issues

The Journal

Cover

Aims and Scope

Subscription Information

Editorial Board

Instructions for Author

Contact Us

 

 

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  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, Burkard--Hammer condition, Burkard--Hammer graph, hamiltonian graph, maximal nonhamiltonian split graph.

 

 

 

 

 

 

Established by Vietnam Academy of Science and Technology & Vietnam Mathematical Society

Published by Springer since January 2013