Necessary and sufficient condition for Maximal uniquely Hamiltonian graph

Abstract

A graph is called a maximal uniquely Hamiltonian graph if it has the maximum number of edges among the graphs with the same number of vertices and exact one Hamiltonian cycle. In this paper we present a necessary and sufficient condition for Maximal uniquely Hamiltonian graph and propose a polynomial time algorithm to recognize the maximal uniquely Hamiltonian graph.

Keywords: Hamiltonian cycle, Maximal uniquely Hamiltonian graph, Sheehan graph, Split Hamiltonian graph, 1-tough graph.