#### Vol. 2, No. 1, 2009

 Recent Issues
 The Journal About the Journal Editorial Board Subscriptions Editors’ Interests Scientific Advantages Submission Guidelines Submission Form Ethics Statement Editorial Login ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Hamiltonian labelings of graphs

### Willem Renzema and Ping Zhang

Vol. 2 (2009), No. 1, 95–114
##### Abstract

For a connected graph $G$ of order $n$, the detour distance $D\left(u,v\right)$ 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\left(G\right)\to ℕ$ such that $|c\left(u\right)-c\left(v\right)|+D\left(u,v\right)\ge n$ for every two distinct vertices $u$ and $v$ of $G$. The value $hn\left(c\right)$ 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\left(G\right)$ 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\left(F\right)$ 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\ge 3$, let ${\mathsc{ℋ}}_{k}$ be the set of connected graphs $G$ for which there exists a Hamiltonian graph $H$ of order $k$ such that $H\subset G\subseteq cor\left(H\right)$. It is shown that $2k-1\le hn\left(G\right)\le k\left(2k-1\right)$ for each $G\in {\mathsc{ℋ}}_{k}$ and that both bounds are sharp.

##### Keywords
Hamiltonian labeling, detour distance
##### Mathematical Subject Classification 2000
Primary: 05C12, 05C45
Secondary: 05C78, 05C15