EUVIMEDEUVIMED entdecken
Crossref

A note on distance labeling of graphs

Carl Johan Casselgren, Anders Henricsson

Opuscula Mathematica · 2025 · 723-738

DOI: 10.7494/opmath.2025.45.6.723 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Opuscula Mathematica, 2025. Verfasst von Carl Johan Casselgren und 1 weiteren Autor:innen. Die Arbeit nennt 7 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Casselgren, C. J., & Henricsson, A. (2025). A note on distance labeling of graphs. Opuscula Mathematica, 723-738. https://doi.org/10.7494/opmath.2025.45.6.723

Vancouver

Casselgren CJ, Henricsson A. A note on distance labeling of graphs. Opuscula Mathematica. 2025:723-738. doi:10.7494/opmath.2025.45.6.723

BibTeX
@article{Casselgren2025,
  author = {Casselgren, Carl Johan and Henricsson, Anders},
  title = {A note on distance labeling of graphs},
  journal = {Opuscula Mathematica},
  year = {2025},
  pages = {723--738},
  doi = {10.7494/opmath.2025.45.6.723}
}
Kostenlos starten →