Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Opuscula Mathematica

1 2025

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A note on distance labeling of graphs

Casselgren Carl Johan, Henricsson Anders

Opuscula Mathematica

2025

Vol. 45, no. 6

723--738

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.