Radio Mean Labeling Algorithm, Its Complexity and Existence Results

Meera Saraswathi, K. N. Meera () and Yuqing Lin
Additional contact information
Meera Saraswathi: Department of Mathematics, School of Physical Sciences, Amrita Vishwa Vidyapeetham, Kochi 682024, India
K. N. Meera: Department of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Bengaluru 560035, India
Yuqing Lin: School of Information and Physical Sciences, College of Engineering, Science and Environment, The University of Newcastle, Callaghan, NSW 2308, Australia

Mathematics, 2025, vol. 13, issue 13, 1-22

Abstract: 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.

Keywords: approximation algorithm; channel assignment problem; graph labeling; integer programming; radio labeling; radio mean labeling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/13/2057/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/13/2057/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:13:p:2057-:d:1684023

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().