Improved lower and upper bounds on the span of distance labeling for some infinite regular grids

Abstract

The channel assignment problem, popularly known as CAP, is one of the elementary and much studied topic in the field of wireless communication. The basic purpose for studying CAP is to find out solutions such that wireless communication becomes interference free with using spectrum as less as possible during the communication. Often the CAP is modeled as an L(k1, . . . , kℓ)-vertex (edge) labeling problem of a graph, where k1, . . . , kℓ are non-negative integers. In L(k1, . . . , kℓ)-vertex (edge) labeling problem, labels are assigned to the vertices (edges) of a graph in such a way that the absolute difference between the labels assigned to any pair of vertices (edges) located at distance i, 1 ≤ i ≤ ℓ, is ki. One of the objective of L(k1, . . . , kℓ)- vertex (edge) labeling of a graph G is to find a labeling of the vertices (edges) such that the span for the corresponding labeling is minimum among all L(k1, . . . , kℓ)- vertex (edge) labelings of G, where span denotes the difference between maximum and minimum labels used for a labeling. Regular grid graphs are common choices for modeling CAP because of their natural resemblance to cellular network for regular geometric pattern. Consequently, various studies of L(k1, k2, . . . , kℓ)-vertex (edge) labeling have been done for infinite regular grids such as infinite hexagonal (T3), square (T4), triangular (T6) and infinite 8-regular grid (T8) grids. In this thesis, we first derive the exact values of the span of L(1, 2)-edge labeling problem for T3 and T4. Then we improve the lower bound on the span of L(1, 2)-edge labeling problem for T6. Next by improving the lower bound, we derive the exact value of the span of L(1, 2)-edge labeling of T8. Next we attempt to derive theoretically the lower bound on the span of L(k1, k2)-vertex labeling problem for T6 for k1 ≤ k2. For this problem, the previous results were obtained partially through computer simulations. We find that our theoretically obtained results exactly coincide with the known results for the sub interval 0 ≤ k1 k2 ≤ 1 3 but provide loose bound for the other sub interval 1 3 ≤ k1 k2 ≤ 1. Next we derive improved lower bound on the span of L(2, 1)-edge labeling problem for T6. Next we study the L(1|, 1,{.z. . , 1} ℓ )-vertex labeling problem for T3. The exact value of the span of L(1|, 1,{.z. . , 1} ℓ )-vertex labeling problem for T3 has not been determined yet for any even ℓ ≥ 8, rather the value of the span was conjectured. We prove this conjecture for ℓ ≥ 8. In all the cases we analyze the structural properties of the underlined graphs and based on which the results are obtained theoretically.