A note on distance labeling of graphs

Carl Johan Casselgren
Anders Henricsson

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.

Keywords: graph labeling, distance labeling.

Mathematics Subject Classification: 05C78.

Full text (pdf)