A note on distance labeling of graphs

• Autorzy: Casselgren Carl Johan , Henricsson Anders

Identyfikatory

DOI

10.7494/OpMath.2025.45.6.723

• Języki publikacji: EN

Abstrakty

EN

We study labelings of connected graphs G using labels 1, . . . , |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) < d(x, y) ⇒ c(u, v) ≤ 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) ≤ 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 ldc(G) of G; if 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 ldc(G) for various classes of graphs. In particular, we prove that for all k, n satisfying 4 ≤ k ≤ n there is a graph G with n vertices and ldc(G) = k, and demonstrate that there are large classes of graphs G satisfying ldc(G) = 1. Indeed, we prove that almost every graph have this property, which implies that graphs G satisfying ldc(G) > 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.

Słowa kluczowe

EN

graph labeling; distance labeling

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2025
• Tom: Vol. 45, no. 6
• Strony: 723--738
• Opis fizyczny: Bibliogr. 7 poz.

Twórcy

autor

Casselgren Carl Johan

• Department of Mathematics, Linköping University, SE-581 83 Linköping, Swed

autor

Henricsson Anders

• Department of Mathematics, Linköping University, SE-581 83 Linköping, Swed

Bibliografia

• [1] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. (2022), DS6.
• [2] S.P.C. Gavoille, D. Peleg, R. Raz, Distance labeling in graphs, J. Algorithms 54 (2001), 85–112.
• [3] A. Henricsson, Distance consistent labellings and the local list number, Bachelor thesis, Linköping University, 2023.
• [4] H. Lennerstad, M. Eriksson, List graphs and distance-consistent node labelings, Electron. J. Graph Theory Appl. 6 (2018), 152–165.
• [5] D.D.-F. Liu, X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Disc. Math. 19 (2005), 610–621.
• [6] D. Peleg, Proximity-preserving labeling schemes and their applications, Lecture Notes in Computer Science 1665 (1999), 30–41.
• [7] M. Thorup, S. Alstrup, H. Kaplan, U. Zwick, Adjacency labeling schemes and induced universal graphs, SIAM J. Disc. Math. 33 (2019), 116–137.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025)