List graphs and distance-consistent node labelings

Abstract

In this paper we consider node labelings c of an undirected connected graph G = (V, E) with labels {1, 2, ..., ∣V∣}, which induce a list distance c(u, v) = ∣c(v) − c(u)∣ besides the usual graph distance d(u, v). Our main aim is to find a labeling c so c(u, v) is as close to d(u, v) as possible. For any graph we specify algorithms to find a distance-consistent labeling, which is a labeling c that minimize $\sum\limits_{u,v\in V} (c(u,v)-d(u,v)) ^2$. Such labeliings may provide structure for very large graphs. Furthermore, we define a labeling c fulfilling d(u₁, v₁) < d(u₂, v₂) ⇒ c(u₁, v₁) ≤ c(u₂, v₂) for all node pairs u₁, v₁ and u₂, v₂ as a list labeling, and a graph that has a list labeling is a list graph. We prove that list graphs exist for all n = ∣V∣ and all k = ∣E∣ : n − 1 ≤ k ≤ n(n − 1)/2, and establish basic properties. List graphs are hamiltonian, and show weak versions of properties of path graphs.