Radio Mean Labeling Algorithm, Its Complexity and Existence Results

Radio mean labeling of a connected graph G is an assignment of distinct positive integers to the vertices of G satisfying a mathematical constraint called radio mean condition. The maximum label assigned to any vertex of G is called the s p a n of the radio mean labeling. The minimum s p a n of all feasible radio mean labelings of G is the radio mean number of G , denoted by r m n ( G ) . In our previous study, we proved that if G has order n , then r m n ( G ) ∈ [ n , r m n ( P n ) ] where P n is a path of order n . All graphs of diameters 1, 2 and 3 have the radio mean number equal to order n . However, they are not the only graphs on n vertices with radio mean number n . Graphs isomorphic to path P n are the graphs having the maximum diameter among the set of all graphs of order n and they possess the maximum feasible radio mean number. In this paper, we show that, for any integer in the range of achievable radio mean numbers, there always exists a graph of order n with the given integer as its radio mean number. This is approached by introducing a special type of tree whose construction is detailed in the article. The task of assigning radio mean labels to a graph can be considered as an optimization problem. This paper critiques the limitations of existing Integer Linear Programming (ILP) models for assigning radio mean labeling to graphs and proposes a new ILP model. The existing ILP model does not guarantee that the vertex labels are distinct, positive and satisfy the radio mean condition, prompting the need for an improved approach. We propose a new ILP model which involves n 2 constraints is the input graph’s order is n . We obtain a radio mean labeling of cycle of order 10 using the new ILP. In our previous study, we showed that, for any graph G , we can extend the radio mean labelings of its diametral paths to the vertex set of G and obtain radio mean labelings of G . This insight forms the basis for an algorithm presented in this paper to obtain radio mean labels for a given graph G with n vertices and diameter d . The correctness and complexity of this algorithm are analyzed in detail. Radio mean labelings have been proposed for cryptographic key generation in previous works, and the algorithm presented in this paper is general enough to support similar applications across various graph structures.