A note on distance labeling of graphs

Abstract

We study labelings of connected graphs $G$ using labels $1,\ldots,|V(G)|$ encoding the distances between vertices in $G$. Following Lennerstad and Eriksson [Electron. J. Graph Theory Appl. 6 (2018), 152-165], we say that a graph $G$ which has a labeling $c$ satisfying that $d(u,v) \lt d(x,y) \Rightarrow c(u,v) \leq c(x,y)$, where $c(u,v) = |c(u) - c(v)|$, is a list graph. We show that these graphs are very restricted in nature and enjoy very strong structural properties. Relaxing this condition, we say that a vertex $u$ in a graph $G$ with a labeling $c$ is list-distance consistent if $d(u,v) \leq d(u,w)$ holds for all vertices $v$, $w$ satisfying that $c(u,w) = c(u,v)+1$. The maximum $k$ such that $G$ has a labeling where $k$ vertices are list-distance consistent is the list-distance consistency $\operatorname{ldc}(G)$ of $G$; if $\operatorname{ldc}(G) = |V(G)|$, then $G$ is a local list graph. We prove a structural theorem characterizing local list graphs implying that they are a quite restricted family of graphs; this answers a question of Lennerstad. Furthermore, we investigate the parameter $\operatorname{ldc}(G)$ for various classes of graphs. In particular, we prove that for all $k$, $n$ satisfying $4 \leq k \leq n$ there is a graph $G$ with $n$ vertices and $\operatorname{ldc}(G)=k$, and demonstrate that there are large classes of graphs $G$ satisfying $\operatorname{ldc}(G) = 1$. Indeed, we prove that almost every graph have this property, which implies that graphs $G$ satisfying $\operatorname{ldc}(G) \gt 1$ are in a sense quite rare (let alone local list graphs). We also suggest further variations on the topic of list graphs for future research.