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 a Hamiltonian labeling of G. In this paper, we survey results and open questions on Hamiltonian labelings of graphs. Furthermore, the Hamiltonian labelings of all complete multipartite graphs are determined and the Hamiltonian labelings of trees are studied.
展开▼
