Upper Bound of Radio Span for Shadow-path Network and Its Mathematical Modeling

Abstract

  Motivated by the frequency assignment problem, we investigate radio labeling of graphs. In graph theory and discrete mathematics, radio labeling of graphs has great attention as it is of immense importance for numerous applications to a wide range of areas such as circuit and sensor network, signal processing, design, frequency assignment in mobile communication systems, etc.  An assignment of labels satisfying specific constraints to the edges, vertices, or both of graph  G  is known as graph labeling. Radio labeling of a graph  G  is a technique of labeling vertices of G  by non-negative integers. Hence, radio labeling problem presents an efficient graph modeling for the frequency assignment problem.  In radio labeling of a graph G,  the maximum label used for labeling vertices is called the span of that radio labeling. The minimum span from all radio labelings of  G is known as the radio number of  G. That radio number reflects the efficient usage of the available frequencies in frequency assignment for a network modeled by the graph G .  This paper studies the radio labeling of network modeled by the shadow of path graphs. We present a mathematical approach to determine an upper bound for radio number of such graphs. Moreover, an integer linear programing model is suggested for calculating such upper bound. Beside that a computational study has been conducted wherein it   showed that our results outperform previous ones published in the literature.