N-Set Distance-Labelings for Cycle Graphs

Abstract

Let G = (V, E) be a graph and C m be the cycle graph with m vertices. In this paper, we continued Yeh’s work [ 1 ] on the distance labeling of the cycle graph C m . 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) (C m ) for all m and λ 1 (n) (C m ) 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) (C m ) . 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 = 3 up to n = 500 by this same algorithm, which indicated that the upper bound is the same as the lower bound for n ≤ 500 .