On Hamiltonian labelings of graphs. (English) Zbl 1225.05158

Renzema, Willem; Zhang, Ping

J. Comb. Math. Comb. Comput. 74, 143-159 (2010).

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

MSC:

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

Keywords:

Hamiltonian labeling, detour distance