Let G = (V, E) be a graph and C<sub>m</sub> 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</sub>. An n-set distance lab...Let G = (V, E) be a graph and C<sub>m</sub> 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</sub>. 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 λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) 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</sub>(n)</sup>(C<sub>m</sub>). 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.展开更多
文摘Let G = (V, E) be a graph and C<sub>m</sub> 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</sub>. 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 λ<sub>1</sub><sup>(n)</sup>(G). Basic results were presented in [1] for λ1</sub>(2)</sup>(C<sub>m</sub>) for all m and λ1</sub>(n)</sup>(C<sub>m</sub>) 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</sub>(n)</sup>(C<sub>m</sub>). 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.
