On the Number of Hamiltonian Cycles in Hamiltonian Dense Graphs

E. A. Okolnishnikova

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Let $G$ be a Hamiltonian graph with $n$ vertices and $Cn(n-1)/2$ edges, where $3/4<C\le 1$. We show that $G$ contains at least $(C_1n)^{C_2n}$ Hamiltonian cycles, where $C_1$ and $C_2$ are some constants depending on $C$, and prove an analog of Dirac's theorem for graphs with prescribed edges.

Key words: Hamiltonian graph, Hamiltonian cycle, Dirac's theorem.

UDC: 519.175.3+519.174.2+519.714.4

Received: 11.01.2005

 English version: Siberian Advances in Mathematics, 2006, 16:4, 79–85

Bibliographic databases:

•