TITLE:
N-Set Distance-Labelings for Cycle Graphs
AUTHORS:
Alissa Shen, Jian Shen
KEYWORDS:
Graph, Channel Assignment, Distance Labeling, Cycle Graph
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.12 No.3,
July
29,
2022
ABSTRACT: Let G = (V, E) be a graph and Cm be the cycle graph with m vertices. In this paper, we continued Yeh’s work [1] on the distance labeling of the cycle graph Cm. An n-set distance labeling of a graph G is the labeling of the vertices (with n labels per vertex) of G under certain constraints depending on the distance between each pair of the vertices in G. Following Yeh’s notation [1], the smallest value for the largest label in an n-set distance labeling of G is denoted by λ1(n)(G). Basic results were presented in [1] for λ1(2)(Cm) for all m and λ1(n)(Cm) for some m where n ≥ 3. However, there were still gaps left unstudied due to case-by-case complexities. For these uncovered cases, we proved a lower bound for λ1(n)(Cm). Then we proposed an algorithm for finding an n-set distance labeling for n ≥ 3 based on our proof of the lower bound. We verified every single case for n = 3up to n = 500by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500.