CONDITIONS FOR GRAPHS ON n VERTICES WITH THE SUM OF DEGREES OF ANY TWO NONADJACENT VERTICES EQUAL TO n-2 TO BE A HAMILTONIAN GRAPH

Abstract

Let G be an undirected simple graph on \(n \geq 3\) vertices with the degree sum of any two nonadjacent vertices in G equal to \(n - 2\). We determine the condition for G to be a Hamiltonian graph.

Keywords

• Connected graph
• Hamiltonian graph
• Independent set
• Regular graph
• t-tough graph.