TY  - JOUR
ID  - Casselgren2025
LB  - Casselgren2025
AU  - Casselgren, Carl Johan
AU  - Henricsson, Anders
TI  - A note on distance labeling of graphs
ST  - A note on distance labeling of graphs
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2025
VL  - 45
IS  - 6
SP  - 723
EP  - 738
DO  - https://doi.org/10.7494/OpMath.2025.45.6.723
UR  - https://doi.org/10.7494/OpMath.2025.45.6.723
AB  - 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.
KW  - graph labeling
KW  - distance labeling
SN  - 1232-9274
ER  -