RECOGNIZING THE HAMILTONIAN GRAPH WITH IS AN EASY PROBLEM
An D. Nhu · International Journal of Advanced Research in Computer Science · 2019
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.