Necessary and sufficient condition for Maximal uniquely Hamiltonian graph

Main Article Content

An D. Nhu
Hoa V. Dinh

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.

Downloads

Download data is not yet available.

Article Details

Section
Articles