RECOGNIZING THE HAMILTONIAN GRAPH WITH IS AN EASY PROBLEM
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
Full Text:
PDFReferences
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.
Copyright (c) 2019 International Journal of Advanced Research in Computer Science

