# A Novel Mathematical Model for Radio Mean Square Labeling Problem

Authors: Elsayed Badr; Shokry Nada; Mohammed M. Ali Al-Shamiri; Atef Abdel-Hay; Ashraf ELrokh
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A radio mean square labeling of a connected graph is motivated by the channel assignment problem for radio transmitters to avoid interference of signals sent by transmitters. It is an injective maph from the set of vertices of the graph G to the set of positive integers N, such that for any two distinct vertices x,y, the inequality dx,y+hx2+hy2/2≥dimG+1 holds. For a particular radio mean square labeling h, the maximum number of hv taken over all vertices of G is called its spam, denoted by rmsnh, and the minimum value of rmsnh taking over all radio mean square labeling h of G is called the radio mean square number of G, denoted by rmsnG. In this study, we investigate the radio mean square numbers rmsnPn and rmsnCn for path and cycle, respectively. Then, we present an approximate algorithm to determine rmsnG for graph G. Finally, a new mathematical model to find the upper bound of rmsnG for graph G is introduced. A comparison between the proposed approximate algorithm and the proposed mathematical model is given. We also show that the computational results and their analysis prove that the proposed approximate algorithm overcomes the integer linear programming model (ILPM) according to the radio mean square number. On the other hand, the proposed ILPM outperforms the proposed approximate algorithm according to the running time.


---

## Body

## 1. Introduction

In wireless networks, each radio station assigns a number called frequency. When different transmitters of district stations send signals, the receiver might get unnecessarily interference of the signals sent by transmitters in particular with close frequencies. This is the channel assignment problem introduced by Hale [1] in 1980 to minimize such interference. In 2001, Chartrand et al. [2] proposed converting this problem to graph theoretical problem using vertex labeling. Many researchers involved with this problem [3–16] and produced different methods to minimize the interference of signals [7]. Recently, Ramesh et al. [8] proposed a new method called radio mean square labeling, which is defined as follows. A radio mean square labeling of a connected graph G is an injective function h from its vertex set V to the set of natural numbers N, such that for any two distinct vertices x and y, hx2+hy2/2≥diamG+1−dx,y holds, where dx,y denotes the distance between the two vertices, and dimG represents the diameter of the graph [8]. For a radio mean square labeling h, the maximum number of hv taken over all vertices of G is called its spam, denoted by rsmnh, and the minimum value of rmsnh taking over all radio mean square labeling h of G is called the radio mean square number of G, denoted as rmsnG. The radio mean square number of h, denoted by rmsnh is the maximum number assigned to any vertex of G. Ramesh et al. [8] determined the radio mean square number for some graphs such as in the centric subdivision of spoke wheel graph and biwheel graph.Due to most of nontrivial coloring models, graph coloring is an NP-hard problem. Therefore, we take into consideration a graph coloring algorithm [9–11]. The judgment of the performance of the used algorithm does include its effectiveness and accuracy for a large number of vertices and the level of complexity regarding suboptimal solutions [12, 13]. Here, we introduce an approximate algorithm that leads to an upper bound of the radio mean square for a large number of vertices. Finally, we turn our attention to reformulate the radio square labeling as a linear programming model and then minimize the suggested linear function. We use of transforming the nonlinear constraint to become a linear constraint by using of some large integers dependably on the coefficient range of the given problem under path calculating conditions. Some illustrated examples and comparison between the techniques will be given.It should be noted that all the considered graphs in this study are finite, simple, connected, and undirected.The organization of the study goes as follows: in Section2, the radio mean square number of cycles and paths are given. Section 3 is devoted to present an approximate algorithm that finds the upper bound of the radio mean square number of a given graph and an illustrative example is included. Section 4 deals with a new mathematical model for finding the upper bound of the radio mean square number of the given graph. Section 5 provides the experimental results. Analysis and statistical tests between the mathematical model and the proposed approximate algorithm are provided. The last section is considered for conclusion.


## 2. Results

The following theorem is about thermsn for the path Pn, and next, we will get the rmsn for cycle Cn.Theorem 1.
For the pathPn, n≥1, and the radio mean square number is(1)rmsnPn=n+k;1≤n≤15andk=0,16≤n≤22andk=1,23≤n≤32andk=2,33≤n≤44andk=3,45≤n≤58andk=4,59≤n≤73andk=5,74≤n≤92andk=6,⋮k2+5k+9≤n≤k2+7k+14,k≥7.Proof.
Clearly,diamPn=n−1. Then, one can define h:VPn⟶N as follows:Case a.
For(2)1≤n≤15,k=0,16≤n≤22,k=1,23≤n≤32,k=2,33≤n≤44,k=3,45≤n≤58,k=4,59≤n≤73,k=5,74≤n≤92,k=6.
One may label the vertices ofPn as follows:Subcase a.1:n is even:(3)hx1=1,hxn=k+2,hx2+i=n+k−2i,0≤i<n2−1,hxn−1−i=n+k−1−2j,0≤j<n2−1.Subcase a.1:n is odd:(4)hx1=1,hxn=k+2,hx2+i=n+k−2i,0≤i<n−12,hxn−1−i=n+k−1−2j,0≤j<n−12−1.Case 2.
bForn≥93 and k2+5k+9≤n≤k2+7k+14,k≥7, one may label the vertices of Pn as the following subcases:Subcase b.1:n is even:(5)hx1=1,hxn=k+2,hx2+i=n+k−2i,0≤i<n2−1,hxn−1−i=n+k−1−2j,0≤j<n2−1.Subcase b.1:n is odd:(6)hx1=1,hxn=k+2,hx2+i=n+k−2i,0≤i<n−12,hxn−1−i=n+k−1−2j,0≤j<n−12−1.
Therefore, for any pairxi,xj,i≠j,0≤i,j≤n, we have dxi,xj+hxi2+hxj2/2≥1+n−1=1+dimPn.
Hence,h is a valid radio mean square labeling for Pn, and therefore, rmsnPn≤rmsnh=n+k. Since h is injective, rmsnPn=n+k,n≥1 for all radio mean square labeling h, and hence, rmsnPn=n+k,n≥1. Therefore, the labeling h defined above satisfies the radio mean square condition.Example 1.
The radio mean square numbers ofP9,P10,P96, and P115 are shown in Figure 1. It is clear that k=0 for P9 and P10, but k=7 for P96, and P115.Figure 1
The radio mean square number ofP9,P10,P96, and P115. (a) rmsn(P9) = 9. (b) rmsn(P10) = 10. (c) rmsn(P96) = 103. (d) rmsn (P115) = 122.
(a)(b)(c)(d)Theorem 2.
The radio mean square numbers of the cyclesCn, n≥3, are given by(7)rmsnCn=n:3≤n≤7,n+k;8≤n≤15andk=0,16≤n≤27andk=1,28≤n≤43andk=2,⋮k2+5k+9≤n≤k2+7k+14,k≥3.Proof.
It is clear that the dimension ofCn=x1,x2,⋯,xn is n/2 since its length is n. Then, one can define h:VCn⟶N as follows:Case 3.
aFor3≤n≤7, we may label the vertices of Cn by(8)hxi=i;1≤i≤n.Case 4.
bForn≥8, 2k2+2k+4≤n≤2k2+6k+7,k≥0. We may label the vertices of Cn by one of the following subcases:Subcase b.1:n is even:(9)hxn/2=k+1,hxi+1=k+3+2i,0≤i<n2−1,hxn−j=k+2+2j,0≤j<n2..Therefore, for any pairxi,xj,i≠j,1≤i,j≤n, we have dxi,xj+hxi2+hxj2/2≥1+n/2=1+dimCn.Subcase b.2:n is odd:(10)hxn+1/2=k+1,hxi+1=k+2+2i,0≤i<n+12−1,hxn−j=k+3+2j,0≤j<n+12−1.
So, for any pairxi,xj,i≠j,1≤i,j≤n, the following inequality holds dxi,xj+hxi2+hxj2/2≥1+n/2=1+dimCn.
Hence,h is a valid radio mean square labeling for Cn, and therefore,(11)rmsnCn≤rmsnh=n,if3≤n≤7,n+k,jfn≥8and2k2+2k+4≤n≤2k2+6k+7,k≥0.
Sinceh is injective,(12)rmsnCn≥n,if3≤n≤7,n+k,jfn≥8,and2k2+2k+4≤n≤2k2+6k+7,k≥0.
For all radio mean square labelingh,(13)rmsnCn=n,if3≤n≤7,n+k,jfn≥8,and2k2+2k+4≤n≤2k2+6k+7,k≥0.
Therefore, the labelinghdefined above satisfies the radio mean square condition.Example 2.
The radio mean square numbers of cyclesC8,C9,C16, and C17 are shown in Figure 2. It is clear that k=1 for C16 and C17, but k=7 for C95 andC112.Figure 2
The radio mean square number of cyclesC8,C9,C16, and C17. (a) rmsn(C16) = 17. (b) rmsn(C17) = 18. (c) rmsn(C95) = 100. (d) rmsn(C112) = 117.
(a)(b)(c)(d)


## 3. A Novel Graph Radio Mean Square Algorithm

Here, we introduce an approximated algorithm. This algorithm finds an upper bound of the radio mean square for arbitrary graphG. The main idea is to labeling some vertices (initial vertices) by floordiam. On the other hand, the algorithm chooses a different vertex as an initial vertex in each iteration.The time complexity of an algorithm is defined as the number of instructions of this algorithm multiplied by the running time of each instruction. The time complexity is considered as a good metric to evaluate the given algorithm. Thus, Algorithm1 has nine steps, and both Step 1 and Step 2 have the same instruction. Step 3 has a nested loop that has On2 time complexity. On the other hand, Step 4, Step 5, and Step 6 have On time complexity. Step 7 has one instruction, while Step 8 and Step 9 have On3 and On4, respectively. Therefore, Algorithm 1 has the time complexity On4.Algorithm 1: Finding an upper bound of the radio mean square number of a graph G.
Input:G be an n-vertex graph, simple connected graph, and the diameter of diamOutput: an upper bound of radio mean square number of GBeginStep 1: choose a vertex u and colu=floordiamStep 2:S=uStep 3: for all v∈VG−S, computetempv=maxt∈scolt+ceilmaxD+1−du,v,1/diamStep 4: let min=minv∈VG−StempvStep 5: choose a vertex v∈VG−S, such thattempv=minStep 6: give colv=minStep 7:S=S∪vStep 8: repeat Step 3–Step 6 until all vertices are labelledStep 9: repeat Step 1–Step 7 for every vertex x∈VGEndIn the coming example, we show and explain how to compute the radio mean square labeling problem forP5.Example 3.
Suppose thatxi is the label of the vertex vi, 1≤i≤5. Therefore, 1 explores an upper bound of the radio mean square labeling problem as follows:
It is known thatdiamP5=4. We select a vertex x1 and colx1=2. Let S=x1, and for all v∈VG−S, compute(14)tempx2=maxx12+ceilmax4+1−1,14=3,tempx3=maxx12+ceilmax4+1−2,14=3,tempx4=maxx12+ceilmax4+1−3,14=3,tempx5=maxx12+ceilmax4+1−4,14=3.
Letmin=minv∈VG−Stempv=3; we choose a vertex x2∈VG−S, such that tempx2=3. Give colx2=3 and S=x1,x2.(15)tempx3=maxx1,x22+ceilmax4+1−2,143+ceilmax4+1−1,14=4,tempx4=maxx1,x22+ceilmax4+1−3,143+ceilmax4+1−2,14=4,tempx5=maxx1,x22+ceilmax4+1−4,143+ceilmax4+1−3,14=4.
Letmin=minv∈VG−Stempv=4; we choose a vertex x3∈VG−S, where tempx3=4. Give colx3=4 and S=x1,x2,x3.(16)tempx4=maxx1,x2,x32+ceilmax4+1−3,143+ceilmax4+1−2,144+ceilmax4+1−1,14=5,tempx5=maxx1,x2,x32+ceilmax4+1−4,143+ceilmax4+1−3,144+ceilmax4+1−2,14=5.
Letmin=minv∈VG−Stempv=5; we choose a vertex x4∈VG−S, where tempx4=5. Give colx4=5 and S=x1,x2,x3,x4.(17)tempx5=maxx12+ceilmax4+1−4,143+ceilmax4+1−3,144+ceilmax4+1−2,145+ceilmax4+1−1,14=6
Letmin=minv∈VG−Stempv=6; we select a vertex x5∈VG−S, where tempx5=6. Give colx5=6 and S=x1,x2,x3,x4,x5. Plainly, all vertices are labelled and rmsnP5=6.


## 4. Formulation of the Radio Mean Square Labeling as a Mathematical Model

In this section, we present the integer linear programming model (ILPM) for the radio mean square labeling problem.LetG be a connected graph of order n with VG=v1,v2,...,vn and let D=dij be the distance matrix of G, that is, dij=dvi;vj for 1≤i,j≤n. Suppose that xi is the label of the vertex vi, 1≤i≤n. Now, we can propose the mathematical model for the radio mean square labeling problem as the ILPM. Let us suppose the function F is F=x1+x2+…+xn.


### 4.1. Formulation 1

Minimize F subject to then2 constraints xi2+xj2/2≥diam+1−dvi,vj for 1≤i≤n−1, 2≤j≤n, and i<j, and as mentioned before, the following steps will transform nonlinear constraints to become linear which is easy to deal with.


### 4.2. Formulation 2

Sincexi2+xj2/2≤xi+xj/22, we have the following inequalities:(18)xi+xj22≥diam+1−dvi−vj,xi+xj2≥diam+1−dvi−vj,xi+xj2≥diam+1−dvi−vj,xi+xj2+1≥diam+1−dvi−vj,Mxi−xj≥xi+xj2+1≥diam+1−dvi−vj.M is a large integer number which depends on the coefficients range of the problem.The absolute value notation is used to get distinct values forxi, where i=1,2,…,n.Now, we can reformulate the radio mean square problem as follows:(19)minF=x1+x2+⋯+xn.Subject toMxi−xj≥diam+1−dvi−vj,(20)1≤i≤n−12≤j≤nandi<j.Here, the floor function is used because the values ofxi,1≤i≤n, are integers.Example 4.
The details of the ILPM to compute the radio mean square labeling forP3. Assume that xi is the label of the vertex vi, such that 1≤i≤3. Thus, the mathematical model for the radio mean square labeling problem as the ILPM is prepared as follows:(21)minf=x1+x2+x3.
Subject to(22)x1−x2≥diam+1−dv1,v2,x1−x3≥diam+1−dv1,v3,x2−x3≥diam+1−dv2,v3,x1,x2,x3≥0.
Sincediam=n−1 and diam=2 for P3,M=1, the distance matrix of P3 is(23)D=012101210.
Therefore, the above mathematical model can be written as follows:(24)minf=x1+x2+x3.
Subject to(25)x1−x2≥1;x1−x3≥1;x2−x3≥1;x1,x2,x3≥0.
The solution of the above model equals to 3.


## 4.1. Formulation 1

Minimize F subject to then2 constraints xi2+xj2/2≥diam+1−dvi,vj for 1≤i≤n−1, 2≤j≤n, and i<j, and as mentioned before, the following steps will transform nonlinear constraints to become linear which is easy to deal with.


## 4.2. Formulation 2

Sincexi2+xj2/2≤xi+xj/22, we have the following inequalities:(18)xi+xj22≥diam+1−dvi−vj,xi+xj2≥diam+1−dvi−vj,xi+xj2≥diam+1−dvi−vj,xi+xj2+1≥diam+1−dvi−vj,Mxi−xj≥xi+xj2+1≥diam+1−dvi−vj.M is a large integer number which depends on the coefficients range of the problem.The absolute value notation is used to get distinct values forxi, where i=1,2,…,n.Now, we can reformulate the radio mean square problem as follows:(19)minF=x1+x2+⋯+xn.Subject toMxi−xj≥diam+1−dvi−vj,(20)1≤i≤n−12≤j≤nandi<j.Here, the floor function is used because the values ofxi,1≤i≤n, are integers.Example 4.
The details of the ILPM to compute the radio mean square labeling forP3. Assume that xi is the label of the vertex vi, such that 1≤i≤3. Thus, the mathematical model for the radio mean square labeling problem as the ILPM is prepared as follows:(21)minf=x1+x2+x3.
Subject to(22)x1−x2≥diam+1−dv1,v2,x1−x3≥diam+1−dv1,v3,x2−x3≥diam+1−dv2,v3,x1,x2,x3≥0.
Sincediam=n−1 and diam=2 for P3,M=1, the distance matrix of P3 is(23)D=012101210.
Therefore, the above mathematical model can be written as follows:(24)minf=x1+x2+x3.
Subject to(25)x1−x2≥1;x1−x3≥1;x2−x3≥1;x1,x2,x3≥0.
The solution of the above model equals to 3.


## 5. Computational Study

In this article, we propose the analysis of the computational results that show the superiority of Algorithm1 on the ILPM according to the radio mean square number. On the other hand, the proposed ILPM outperforms Algorithm 1 according to CPU time.Paths and cycles are used to evaluate the proposed models. The computation environment is given in Table1. MATLAB solver is used to solve the ILPM. In Tables 2 and 3, the following symbols standard RMS, rmsn, and CPU times are used to indicate the exact radio mean square number, the calculated mean square number, and the running time for path and cycles, respectively. The convergence between the calculated and exact upper bounds of the radio mean square number of paths is given in Table 2. Figures 3 and 4 show that the superiority of the proposed Algorithm 1 on the ILPM according to the radio mean square number. For example, the standard radio mean square number for P50 is 54, but it is 56 and 344 by Algorithm 1 and the ILPM, respectively. Figures 5 and show the superiority of the proposed Algorithm 1 on the ILPM according to CPU time. Table 3 provides that the gap between the ILPM and the proposed Algorithm 1 is large according to the radio mean square number. It is clear that 1 is better than the ILPM according to the radio mean square number. According to the CPU time, Tables 2 and 3 explain the superiority of the proposed ILPM on Algorithm 1.Table 1
Description of the computing environment.
CPUIntel (R) Core (TM) i5-2430 CPU at 2.40 GHzRAM size4 GB RAMMATLAB versionR2019a (9.6.0.1072779)Table 2
Comparison between standard radio mean square number, algorithm, and integer linear programming for the upper bound of radio mean square number for the path graph.
Path graphNStandard RMSProposed algorithmInteger linear programmingrmsn (Pn)CPU timermsn (Pn)CPU time11————2220.000156520.01359613330.000749530.01376074440.000924240.01428385560.000925990.01483606670.0011930110.01497017780.0028154130.01516078890.0031659150.015343799100.0086583170.01535301010120.0092995280.01536021111130.0178153310.01546301212140.0179739340.01581221313150.0195242370.01592641414160.0214671400.01606641515170.0323685430.01653121617180.0397062460.01657561718200.0488390650.01667561819210.0521773690.01685931920220.0635412730.01686732021230.0773853770.01730172122240.0926470810.01739822223250.1082337850.01746492325260.1321028890.01765192426270.1680530930.01782092527280.1819503970.01783192628300.21741771260.01784082729310.24232151310.01785022830320.28389891350.01793232931330.33060901420.01812443032340.39074871460.01821505054563.30449643440.0295531Table 3
Comparison between standard radio mean square number, algorithm, and integer linear programming for the upper bound of radio mean square number for the cycle graph.
Cycle graphNStandard RMSProposed algorithmInteger linear programmingrmsn (Cn)CPU timermsn (Cn)CPU time1—————2—————3330.000294630.01217034440.000619840.01286975550.001316450.01306966660.001774660.01343007770.002341970.01373798890.0037564150.0137439910100.0050932170.01406731010110.0060342190.01431741111120.0088211210.01434271212130.0148844230.01472691313140.0172248250.01479851414150.0203240270.01492311515160.0251720290.01510181617170.0323380310.01519291718180.0397318330.01556491819200.0492787520.01560361920210.0612156550.01568562021220.0765414580.01577742122230.0898619610.01602122223240.1191102640.01624202324250.1328831670.01630222425260.1583415700.01653122526270.1758159730.01656482627280.2122978760.01651162728290.2491384790.01662342830300.2822584820.01673522931310.3290932850.01684703032320.3655289880.01718445053543.04685932460.0250638Figure 3
Comparison between standard radio mean square number, algorithm, and integer linear programming for the upper bound of radio mean square number for the path graph.Figure 4
Comparison between standard radio mean square number, algorithm, and integer linear programming for the upper bound of radio mean square number for the cycle graph.Figure 5
Comparison between standard radio mean square number, algorithm, and integer linear programming for the upper bound of radio mean square number for the path graph according to CPU time.


## 6. Conclusions

In this work, we determined the radio mean square numbersrmsnPn and rmsnCn for paths and cycles. Then, the proposed approximate algorithm is introduced to obtain rmsnG for graph G. In addition, a new mathematical model is proposed in order to find the upper bound of rmsnG for graph G, and a comparison between the proposed approximate algorithm and the proposed mathematical model is introduced. Finally, the computational results and their analysis have proved that the proposed approximate algorithm overcomes the ILPM according to the radio mean square number.



---

*Source: 3303433-2022-01-12.xml*