RECOGNIZING THE HAMILTONIAN GRAPH WITH IS AN EASY PROBLEM

An D Nhu

Abstract


Let  be an undirected and single graph on  vertices with , i.e., the degree sum of any two non-adjacent vertices in  is equal to . We show that, recognizing the whether or not  is a Hamiltonian graph can be done in polynomial time.

 

Keywords


Hamiltonian cycle, Hamiltonian graph, 1-tough graph, polynomial algorithm.

Full Text:

PDF

References


Bondy J. A. and Chvátal V., A Method in Graph Theory, Discrete Math. 15, p. 111-135, 1976.

Graham R., Lovász L. and Grotschel M., Handbook of combinatorics, Vol 1, Elsevier Science B.V., 1995.

An D. Nhu, Duong B. Duc, “Some problems about Hamiltonian Cycle in special graphs”, The 2nd International Conference on Theories and Applications of Computer Science (ICTACS’09), Journal of Sciencce and Technology, Vietnam Academy of Science and Technology, Vol. 46, No 5A (2008), 57-66.

An D. Nhu, Hoa V. Dinh, “Necessary and sufficient condition for Maximil uniquely Hamiltonian graph”. International Journal of Advanced Research in Computer Science (IJARCS). Volume 3 No. 5 September-October 2012.




DOI: https://doi.org/10.26483/ijarcs.v10i2.6403

Refbacks

  • There are currently no refbacks.


Bookmark and Share


Copyright (c) 2019 International Journal of Advanced Research in Computer Science