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)→N such that
|c(u)−c(v)|+D(u,v)≥n for every two
distinct vertices
u
and
v of
G. The value
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
hn(G)
of
G
is the minimum value of Hamiltonian labelings of
G.
Hamiltonian labeling numbers of some well-known classes of graphs
are determined. Sharp upper and lower bounds are established for
the Hamiltonian labeling number of a connected graph. The corona
cor(F) of a graph
F is the graph
obtained from
F
by adding exactly one pendant edge at each vertex of
F. For each
integer
k≥3, let
Hk be the set of connected
graphs
G for which there
exists a Hamiltonian graph
H
of order
k
such that
H⊂G⊆cor(H). It
is shown that
2k−1≤hn(G)≤k(2k−1)
for each
G∈Hk
and that both bounds are sharp.
