On Hamiltonian Labelings of Graphs

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) \geq 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.