Radio Mean Labeling Algorithm, Its Complexity and Existence Results
Radio mean labeling of a connected graph <i>G</i> is an assignment of distinct positive integers to the vertices of <i>G</i> satisfying a mathematical constraint called radio mean condition. The maximum label assigned to any vertex of <i>G</i> is called the <in...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-06-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/13/13/2057 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849704234260365312 |
|---|---|
| author | Meera Saraswathi K. N. Meera Yuqing Lin |
| author_facet | Meera Saraswathi K. N. Meera Yuqing Lin |
| author_sort | Meera Saraswathi |
| collection | DOAJ |
| description | Radio mean labeling of a connected graph <i>G</i> is an assignment of distinct positive integers to the vertices of <i>G</i> satisfying a mathematical constraint called radio mean condition. The maximum label assigned to any vertex of <i>G</i> is called the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>s</mi><mi>p</mi><mi>a</mi><mi>n</mi></mrow></semantics></math></inline-formula> of the radio mean labeling. The minimum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>s</mi><mi>p</mi><mi>a</mi><mi>n</mi></mrow></semantics></math></inline-formula> of all feasible radio mean labelings of <i>G</i> is the radio mean number of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mi>m</mi><mi>n</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. In our previous study, we proved that if <i>G</i> has order <i>n</i>, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mi>m</mi><mi>n</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>∈</mo><mo>[</mo><mi>n</mi><mo>,</mo><mspace width="4pt"></mspace><mi>r</mi><mi>m</mi><mi>n</mi><mrow><mo>(</mo><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>]</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>n</mi></msub></semantics></math></inline-formula> is a path of order <i>n</i>. All graphs of diameters 1, 2 and 3 have the radio mean number equal to order <i>n</i>. However, they are not the only graphs on <i>n</i> vertices with radio mean number <i>n</i>. Graphs isomorphic to path <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>n</mi></msub></semantics></math></inline-formula> are the graphs having the maximum diameter among the set of all graphs of order <i>n</i> 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 <i>n</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>n</mi><mn>2</mn></msup></semantics></math></inline-formula> constraints is the input graph’s order is <i>n</i>. 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 <i>G</i>, we can extend the radio mean labelings of its diametral paths to the vertex set of <i>G</i> and obtain radio mean labelings of <i>G</i>. This insight forms the basis for an algorithm presented in this paper to obtain radio mean labels for a given graph <i>G</i> with <i>n</i> vertices and diameter <i>d</i>. 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. |
| format | Article |
| id | doaj-art-74a0fe31efe04b0eb4b4a6c1e347ed0d |
| institution | DOAJ |
| issn | 2227-7390 |
| language | English |
| publishDate | 2025-06-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj-art-74a0fe31efe04b0eb4b4a6c1e347ed0d2025-08-20T03:16:50ZengMDPI AGMathematics2227-73902025-06-011313205710.3390/math13132057Radio Mean Labeling Algorithm, Its Complexity and Existence ResultsMeera Saraswathi0K. N. Meera1Yuqing Lin2Department of Mathematics, School of Physical Sciences, Amrita Vishwa Vidyapeetham, Kochi 682024, IndiaDepartment of Mathematics, Amrita School of Engineering, Amrita Vishwa Vidyapeetham, Bengaluru 560035, IndiaSchool of Information and Physical Sciences, College of Engineering, Science and Environment, The University of Newcastle, Callaghan, NSW 2308, AustraliaRadio mean labeling of a connected graph <i>G</i> is an assignment of distinct positive integers to the vertices of <i>G</i> satisfying a mathematical constraint called radio mean condition. The maximum label assigned to any vertex of <i>G</i> is called the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>s</mi><mi>p</mi><mi>a</mi><mi>n</mi></mrow></semantics></math></inline-formula> of the radio mean labeling. The minimum <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>s</mi><mi>p</mi><mi>a</mi><mi>n</mi></mrow></semantics></math></inline-formula> of all feasible radio mean labelings of <i>G</i> is the radio mean number of <i>G</i>, denoted by <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mi>m</mi><mi>n</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>. In our previous study, we proved that if <i>G</i> has order <i>n</i>, then <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>r</mi><mi>m</mi><mi>n</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>∈</mo><mo>[</mo><mi>n</mi><mo>,</mo><mspace width="4pt"></mspace><mi>r</mi><mi>m</mi><mi>n</mi><mrow><mo>(</mo><msub><mi>P</mi><mi>n</mi></msub><mo>)</mo></mrow><mo>]</mo></mrow></semantics></math></inline-formula> where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>n</mi></msub></semantics></math></inline-formula> is a path of order <i>n</i>. All graphs of diameters 1, 2 and 3 have the radio mean number equal to order <i>n</i>. However, they are not the only graphs on <i>n</i> vertices with radio mean number <i>n</i>. Graphs isomorphic to path <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>n</mi></msub></semantics></math></inline-formula> are the graphs having the maximum diameter among the set of all graphs of order <i>n</i> 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 <i>n</i> 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mi>n</mi><mn>2</mn></msup></semantics></math></inline-formula> constraints is the input graph’s order is <i>n</i>. 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 <i>G</i>, we can extend the radio mean labelings of its diametral paths to the vertex set of <i>G</i> and obtain radio mean labelings of <i>G</i>. This insight forms the basis for an algorithm presented in this paper to obtain radio mean labels for a given graph <i>G</i> with <i>n</i> vertices and diameter <i>d</i>. 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.https://www.mdpi.com/2227-7390/13/13/2057approximation algorithmchannel assignment problemgraph labelinginteger programmingradio labelingradio mean labeling |
| spellingShingle | Meera Saraswathi K. N. Meera Yuqing Lin Radio Mean Labeling Algorithm, Its Complexity and Existence Results Mathematics approximation algorithm channel assignment problem graph labeling integer programming radio labeling radio mean labeling |
| title | Radio Mean Labeling Algorithm, Its Complexity and Existence Results |
| title_full | Radio Mean Labeling Algorithm, Its Complexity and Existence Results |
| title_fullStr | Radio Mean Labeling Algorithm, Its Complexity and Existence Results |
| title_full_unstemmed | Radio Mean Labeling Algorithm, Its Complexity and Existence Results |
| title_short | Radio Mean Labeling Algorithm, Its Complexity and Existence Results |
| title_sort | radio mean labeling algorithm its complexity and existence results |
| topic | approximation algorithm channel assignment problem graph labeling integer programming radio labeling radio mean labeling |
| url | https://www.mdpi.com/2227-7390/13/13/2057 |
| work_keys_str_mv | AT meerasaraswathi radiomeanlabelingalgorithmitscomplexityandexistenceresults AT knmeera radiomeanlabelingalgorithmitscomplexityandexistenceresults AT yuqinglin radiomeanlabelingalgorithmitscomplexityandexistenceresults |