On Hamiltonian Labelings of Graphs

Abstract

For a connected graph $G$ of order $n$, the detour distance $D(u,v)$ between two vertices $u$ and $v$ in $G$ is the length of a longest $u-v$ path in $G$. A Hamiltonian labeling of $G$ is a function $c:V(G)\to \mathbb{N}$ such that

$$|c(u)–c(v)|+D(u,v)\ge n$$

for every two distinct vertices $u$ and $v$ of $G$. The value $\text{hn}(c)$ of a Hamiltonian labeling $c$ of $G$ is the maximum label (functional value) assigned to a vertex of $G$ by $c$; while the Hamiltonian labeling number $\text{hn}(G)$ of $G$ is the minimum value of a Hamiltonian labeling of $G$. We present several sharp upper and lower bounds for the Hamiltonian labeling number of a connected graph in terms of its order and other distance parameters.