The Hamiltonian Number of Graphs with Prescribed Connectivity

Abstract

A Hamiltonian walk in a connected graph $G$ is a closed walk of minimum length which contains every vertex of $G$. The Hamiltonian number $h(G)$ of a connected graph $G$ is the length of a Hamiltonian walk in $G$. Let $\mathcal{G}(n)$ be the set of all connected graphs of order $n$, $\mathcal{G}(n,\kappa =k)$ be the set of all graphs in $\mathcal{G}(n)$ having connectivity $\kappa =k$, and $h(n,k)=\{h(G):G\in \mathcal{G}(n,\kappa =k)\}$. We prove in this paper that for any pair of integers $n$ and $k$ with $1\le k\le n–1$, there exist positive integers $a:=min(h;n,k))=min\{h(G):G\in \mathcal{G}(n,\kappa =k)\}$ and $b:=max(h;n,k))=max\{h(G):G\in \mathcal{G}(n,\kappa =k)\}$ such that $(h;n,k)=\{x\in \mathbb{Z}:a\le x\le b\}$. The values of $min(h;n,k))$ and $max(h(n,k))$ are obtained in all situations.