List graphs and distance-consistent node labelings
Håkan Lennerstad, Mattias Eriksson · Electronic Journal of Graph Theory and Applications · 2018
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 1 , v 1 ) < d ( u 2 , v 2 ) ⇒ c ( u 1 , v 1 ) ≤ c ( u 2 , v 2 ) for all node pairs u 1 , v 1 and u 2 , v 2 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.