The Study of 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 chapter, 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 determined by the distance between each pair of 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 \(\lambda\)₁⁽ⁿ⁾ (G) The basic findings were given in [1] for \(\lambda\)₁⁽²⁾ (C_m) for all m and \(\lambda\)₁⁽ⁿ⁾ (C_m) for some m where n \(\ge\) 3. However, due to case-by-case difficulties, there were still gaps that remained unstudied.  For these uncovered cases, we proved a lower bound for \(\lambda\)₁⁽ⁿ⁾ (C_m). Then we developed an algorithm for finding an n-set distance labeling for n \(\ge\) 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 revealed that the upper bound is the same as the lower bound for n \(\le\) 500. Potential future research application is briefly discussed at the end of this paper.