Results and open problems on Hamiltonian labelings of graphs. (English) Zbl 1206.05087

Okamoto, Futaba; Renzema, Willem; Zhang, Ping

Congr. Numerantium 198, 189-206 (2009).

Summary: 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\). 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.

MSC:

05C78	Graph labelling (graceful graphs, bandwidth, etc.)
05C12	Distance in graphs
05C45	Eulerian and Hamiltonian graphs

Keywords:

detour distance; Hamiltonian labeling