List Graphs and Distance-consistent Node Labelings

Håkan Lennerstad • Mattias Eriksson

Download full text
(English, 14 pages)


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) \Rightarrow c(u_1,v_1) \leq 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\leq k\leq n(n-1)/2, and establish basic properties. List graphs are hamiltonian, and show weak versions of properties of path graphs.




Electronic Journal of Graph Theory and Applications

The Electronic Journal of Graph Theory and Applications (EJGTA) is a refereed journal devoted to ... see more