# Upper Bounds of Radio Number for Triangular Snake and Double Triangular Snake Graphs

Authors: Ashraf ELrokh; Elsayed Badr; Mohammed M. Ali Al-Shamiri; Shimaa Ramadhan
Journal: Journal of Mathematics
 (2022)

---

## Abstract

A radio labeling of a simple connected graphG=V,E is a function h:V⟶N such that hx−hy≥diamG+1−dx,y, where diam G is the diameter of graph and d(x, y) is the distance between the two vertices. The radio number of G, denoted by rnG, is the minimum span of a radio labeling for G. In this study, the upper bounds for radio number of the triangular snake and the double triangular snake graphs are introduced. The computational results indicate that the presented upper bounds are better than the results of the mathematical model provided by Badr and Moussa in 2020. On the contrary, these proposed upper bounds are better than the results of algorithms presented by Saha and Panigrahi in 2012 and 2018.


---

## Body

## 1. Introduction

The field of graph theory assumes a crucial part in different fields. One of the significant regions in graph theory is graph labeling which is used in many applications such as coding theory,x-ray crystallography, radar, astronomy, circuit design, communication network addressing, data base management, and channel assignment problem. The channel assignment problem is the problem of assigning channels (nonnegative integers) to the stations in an optimal way such as the interference is avoided. In [1], Badr and Moussa proposed a work on upper bound of radio k-chromatic number for a given graph against the other which is due to Saha and Panigrahi [2]. Badr and Moussa proposed a new mathematical model for finding the upper bound of a graph [1]. In [3], Saha and Panigrahi introduced another algorithm (with time complexity O(n4)) for determining the upper bound of a graph. Ali et al. gave the upper bound for the radio number of generalized gear graph [4]. Fernandez et al. proved that the radio number of the n-gear is 4n + 2 [5]. Yao et al. were defined as a new graph radio labeling on trees, and the properties of trees labeling were shown [6]. Smitha and Thirusangu determined the radio mean number of double triangular snake graph and alternate double triangular snake graph [7]. If p&q is prime numbers, the radio numbers of zero divisor graphs ΓZP2×Zq were investigated by Ahmad and Haider [8].For more details about how to formulate a problem to a mathematical model, the reader can refer to [9–11]. On the contrary, for more details about other labeling that are related to radio labeling such as radio mean, radio mean square, and radio geometric. The reader is referred to [10, 11].In this current work, the upper bounds for radio number of the triangular snake and the double triangular snake graphs are introduced. The computational results indicate that the presented upper bounds are better than the results of the mathematical model provided by Badr and Moussa [1]. On the contrary, these proposed upper bounds are better than the results of algorithms presented by Saha and Panigrahi [2, 3].


## 2. Materials and Methods

In this section, we introduce some basic definitions before we prove the theorems that determine the upper bounds’ radio of the number for triangular snake and double triangular snake. On the contrary, we introduce the previous works which are related to the determining of the upper bound of radio number of a graph.Definition 1.
(see [12], diameter of graph). The diameter of G is the greatest eccentricity among all vertices of G and it is denoted by diam G.Definition 2.
(see [13], triangular snake). A triangular snake (or Δ-snake) is a connected graph in which all blocks are triangles and the block-cut-point graph is a path.Definition 3.
(see [7], double triangular snake). A double triangular snake D(Tn) is obtained from two triangular snakes with a common path.
In 2013, Algorithm 1 was introduced by Saha and Panigrahi [2] for determining the upper bound of the radio number of a given graph. Algorithm 1 has O(n3) time complexity such that n is the number of the vertices of G. In 2018, Saha and Panigrahi [2] proposed a new algorithm (Algorithm 2) for determining the upper bound of the radio number of a given graph. Algorithm 2 has O(n4) time complexity. On the contrary, in 2020, Badr and Moussa [1] proposed a novel mathematical model which finds the upper bound of the radio number of a given graph.
Algorithm 1: [2] Finding a radio k-coloring of a graph.
Input: G be an n-vertex simple connected graph, k be a positive integer, and the adjacency matrix A[n][n] of GOutput: A radio k-coloring of G.BeginCompute the distance matrixD[n][n] of G using Floyed–Warshall’s algorithm and the adjacency matrix A[n][n] of G.RadioNumber =∞;forl = 1 tondofori = 1 tondolabeling [i] = 0;endfori = 1 tondoforj = 1 tondoc[i][j] = diam + 1 − D[i][j];endc[i][j] = ∞;endfori = 2 tondo/∗find the minimum valuemof the column with positionp∗/[m, p] = min [c(l, :)];forj = 1 tonc[p][j] = c[p][j] + mifc[p][j] < c[l][j]c[p][j] = c[l][j]endendlabeling [p] = ml = pend/∗find the max value of the labeling∗/Max_Value = max (labeling))if RadioNumber > Max_ValueRadioNumber = Max_ValueendendEnd
Algorithm 2: [3] Finding an upper bound of the radio number of a graph G.
Input: G be an n-vertex graph, simple connected graph, and the diameter of diam.Output: an upper bound of radio number of G.BeginStep 1: choose a vertex u and colu=floordiam.Step 2: S=u.Step 3: for all v∈VG−S, computetempv=maxt∈scolt+maxD+1−du,v,1.Step 4: let min=minv∈VG−Stempv.Step 5: choose a vertex v∈VG−S, such that tempv=min.Step 6: give colv=min.Step 7: S=S∪vStep 8: repeat Step 3 to Step 6 until all vertices are labeled.Step 9: repeat Step 1 to Step 7 for every vertex x∈VG.End


## 3. Results and Discussion

Here, we introduce two theorems which determine the upper bounds for radio number of triangular snake and double triangular snake. The presented upper bounds (by Theorems1 and 2) are better than the results of the mathematical model provided by Badr and Moussa [1]. On the contrary, these proposed upper bounds are better than the results of algorithms presented by Saha and Panigrahi [2, 3].Theorem 1.
LetG be a triangular snake graph Δk−snake with k blocks and n vertices, where dx,y≥1; then, the upper bound of the radio number of Δk−snake is defined as follows:(1)rnΔk−snake≤k2+k2,ifkis even,k2+k−k2,ifkis odd,Proof.
To prove this theorem, its suffices to give a distance labelingh of Δk−snake.
Letx1,x2,x3,…,xn be a Δk−snake of length k, i.e., diameter of Δk−snake=k.
Define a functionh:VΔk−snake⟶N as the following cases.Case 1.
k is odd:(2)hxi=hxk+1=0,hxk+1−i=ki,1≤i≤k,hxk+2+j=k2+k2−jk,0≤j≤k−1.
Now, we are in a position to prove that the functionh(x) is the distance labeling of Δk−snake.
For eachi,i+1,(3)ki−ki+1≥diam+1−dx,y,ki−ki+1≥k+1−dx,y,k≥k+1−dx,y.
Also, for eachj,j+1,(4)k2+k2−jk−k2+k2−j+1k≥diam+1−dx,y,k2+k2−jk−k2+k2−jk−k≥k+1−dx,y,k≥k+1−dx,y,k≥k+1−dx,y.
Suppose that1≤i≤k,0≤j≤k−1.
Ifi = j,(5)ki−k2+k2−jk≥k+1−dx,y,k2−2k+k2≥k+1−dx,y,otherwise,(6)k2−k2−k≥k+1−dx,y.Case 2.
k is even is similarly proved:(7)hxi=hxk+1=0,hxk+1−i=ki,1≤i≤k,hxk+2+j=k2+k2−kj,0≤j≤k−1.
We show that the functionh(x) is the distance labeling of Δk−snake.
For eachi,i+1,(8)ki−ki+1≥diam+1−dx,y,ki−ki+1≥k+1−dx,y,k≥k+1−dx,y.
Also, for eachj,j+1,(9)k2+k2−kj−k2+k2−kj+1≥diam+1−dx,y,k2+k2−kj−k2+k2−kj−k≥k+1−dx,y,k≥k+1−dx,y,k≥k+1−dx,y.
Suppose that1≤i≤k,0≤j≤k−1.
Ifi = j,(10)ki−k2+k2−jk≥k+1−dx,y,k2−3k2≥k+1−dx,y,otherwise,(11)k2−12k≥k+1−dx,y.Example 1.
Figure1 presents the labeling Δ3snake according to Theorem 1.Figure 1
The radio number ofΔ3snake.Theorem 2.
LetG be a double triangular snake graph with k blocks and n vertices; then, the upper bound of the radio number of double Δk−snake is defined as follows:(12)rnΔksnake≤3,ifk=1,7,ifk=2,2k2−k+3,ifkis odd,2k2−k+2,ifkis even.Proof.
To prove this theorem, it suffices to give a distance labelingh of double Δk−snake. Notice that the diameter of double triangular snake is the same as the diameter of triangular snake graph. Let x1,x2,x3,…,xn be a 2Δk−snake of length k, where the diameter of 2Δk−snake=kandn=3k+1.
Define a functionh:VdoubleΔk−snake⟶N as the following cases:Fork = 1, let the sufficed labeling hx1=0,hx2=2,hx3=5,andhx4=3Fork = 2, let hx1=4,hx2=2,hx3=0,hx4=5,hx5=3,hx6=6, andhx7=7Case 3.
k is even and k > 2,(13)hxi=hxk+1=0,hxk−i+1=ki,1≤i≤k,hxk+i+2=k2+k2−ki,0≤i≤k−1,x2k+2+i=k2+k+1+k−1i,0≤i≤k−1.
We are in a position to prove that the functionhxi are the distance labeling of double Δk−snake.
For eachi,i+1,(14)ki−ki+1≥diam+1−dx,y,k≥k+1−dx,y.
For eachi,i+1,(15)k2+k2−ki−k2+k2−ki+1≥diam+1−dx,y,k≥k+1−dx,y.
Also, for eachi,i+1,(16)k2+k+1+k−1i−k2+k+1+k−1i+1≥diam+1−dx,y,k−1≥k+1−dx,y.
Now, suppose that1≤i≤kand0≤j≤k−1:(17)ki−k2+k2−kj≥diam+1−dx,y,k2+3k2≥k+1−dx,y.
Suppose that1≤i≤kand0≤j≤k−1:(18)ki−k2+k+1+k−1j≥diam+1−dx,y,k2−k+2≥k+1−dx,y.
Ifi = 1 and j = 0,(19)k2+1≥k+1−dx,y,otherwise,(20)k+1≥k+1−dx,y,1≤i≤k−1and0≤j≤k−1,k2+k2−ki−k2+k+1+k−1j≥diam+1−dx,y,2k2−52k+2≥k+1−dx,y.
Ifi = 0 and j = k − 1,(21)2k2−k+2≥k+1−dx,y,otherwise,(22)k2−k2+1≥k+1−dx,y.Case 4.
k is odd and k > 1:(23)hxi=hxk+1=0,hxk−i+1=ki,1≤i≤k,hxk+i+2=k2+k+12−ki,0≤i≤k−1,x2k+2+i=k2+k+2−k−1i,0≤i≤k−1.
For eachi,i+1,(24)ki−ki+1≥diam+1−dx,y,k≥k+1−dx,y.
For eachi,i+1,(25)k2+k+12−ki−k2+k+12−ki+1≥diam+1−dx,y,k≥k+1−dx,y.
Also, for eachi,i+1,(26)k2+k+2−k−1i−k2+k+2−k−1i+1≥diam+1−dx,y,k−1≥k+1−dx,y.
Now, suppose that1≤i≤kand0≤j≤k−1:(27)ki−k2+k+12−kj≥diam+1−dx,y,k2−3k2−12≥k+1−dx,y,otherwise,(28)ki−k2+k+12−kj≥diam+1−dx,y,k2+12≥diam+1−dx,y.
Suppose that1≤i≤kand0≤j≤k−1:(29)ki−k2+k+2−k−1j≥diam+1−dx,y,k2−3k−1≥k+1−dx,y.
Ifi = 1 and j = k − 1,(30)2k−1≥k+1−dx,y,otherwise,(31)ki−k2+k+2−k−1j≥diam+1−dx,y,k+2≥k+1−dx,y.
Suppose that0≤i≤k−1and0≤j≤k−1:(32)k2+k+12−ki−k2+k+2−k−1j≥diam+1−dx,y,32k+12≥k+1−dx,y.
Ifi = 0 and j = k − 1,(33)k2+k+12−ki−k2+k+2−k−1j≥diam+1−dx,y,k2−52k−12≥k+1−dx,y,otherwise,(34)k2−12k+32≥k+1−dx,y.Example 2.
Figure2 presents the labeling double triangular Δ3snake according to Theorem 2.Figure 2
The radio number of double triangularΔ3snake.


## 4. Computational Study

In order to evaluate the proposed upper bounds presented by Theorems1 and 2, we make a numerical experiment between the proposed results and the results of [1–3]. This experiment applies on two graphs (triangular snake and double triangular snake). The description of the environment is as follows: MATLAB R2016a with default options and all runs were carried out under MS Windows 7 Professional system, having Intel® Core™ i3-3217U CPU@1.80 GHz and 4 Gb RAM.In Tables1 and 2, the abbreviations Ub0, Ub1, Ub2, and Ub3 are used to denote upper bounds are due to the works of Saha and Panigrahi [2], Saha and Panigrahi [3], Badr and Moussa [1], and the proposed algorithm, respectively.Table 1
Comparison between standard radio number and the upper bound of radio number for the triangular snake graph.
knUB0 [2]UB1 [3]UB2 [1]UB3rnCPU timernCPU timernCPU timernCPU time1320.00770420.004075520.00173782O(1)2560.00436450.00425560.0023825O(1)37120.00612120.00555140.00526511O(1)49200.024677180.012055260.00536418O(1)511300.051972300.013155420.00565928O(1)613420.230102390.013621620.00579939O(1)715560.307545560.013755860.00690553O(1)817720.308318680.0142981140.00715368O(1)919900.468408900.0147491460.00720386O(1)10211100.7517551050.014931820.00743105O(1)11231320.9247851320.0152012220.007672127O(1)12251561.2197991500.0159882660.008343150O(1)13271821.6749181820.0161053140.008354176O(1)14292102.6895642030.0161973660.008496203O(1)15312403.2244032400.0162014220.008661233O(1)16332723.5672012640.017114820.009033264O(1)17353064.4478753060.0176255460.009587298O(1)18373425.5611393330.0185566140.009701333O(1)19393806.9331083800.0190996860.009929371O(1)20414208.3454234100.0203277620.010011410O(1)214346212.8684854620.0212878420.010364452O(1)224550613.7874224950.0219839260.011044495O(1)234755215.9466425520.02212610140.011472541O(1)244960020.1455235880.02938811060.011726588O(1)255165022.9314276500.04994612020.012145638O(1)265370226.7926386890.05359913020.013162689O(1)275575630.0074777560.05889514060.013417743O(1)285781233.7786897980.06005615140.013437798O(1)295987039.5704088700.08913716260.017043856O(1)306193045.2165779150.14860217420.026953915O(1)501012550342.01140125250.28296418620.2594962525O(1)Table 2
Comparison between standard radio number and for the upper bound of the radio number for the double triangular snake graph.
knUB0 [2]UB1 [3]UB2 [1]UB3rnCPU timernCPU timernCPU timernCPU time1420.00890530.01399420.0071793O(1)2770.00930280.01449480.0080937O(1)310150.012654170.015187190.01017118O(1)413260.01432290.016028360.01122430O(1)516410.022551440.026618590.01273448O(1)619570.022565620.031761880.01469868O(1)722780.024324830.0973351230.01766394O(1)8251000.0263271070.0995991640.025045122O(1)9281270.0307621340.1680362110.025465156O(1)10311550.0380291640.2177852640.031522192O(1)11341880.0489761970.3124013230.032649234O(1)12372220.0585162330.4763303880.033239278O(1)13402620.0673162720.6483004590.039245328O(1)14433010.0926053140.8310505360.043670380O(1)15463470.1018863591.0870816190.045682438O(1)16493920.1576354071.3891417080.052569498O(1)17524440.1639014581.7407258030.065006564O(1)18554950.2705545122.1515529040.131148632O(1)19585530.2875475692.62565710110.156826706O(1)20616100.3250286293.22902111242.637903782O(1)21646750.3500936923.86757712432.655901864O(1)22677370.3559197584.61999013682.676703948O(1)23708080.3692948275.62590414992.6989031038O(1)24738760.4600568996.57024016363.1743211130O(1)25769530.5123829747.55278217793.3213241228O(1)267910270.55315810529.09339219283.5928341328O(1)278211100.625059113310.40406720833.7201721434O(1)288511900.740484121712.81114222444.0192341542O(1)298812800.77942130413.94211524114.8923211656O(1)309113650.974537139416.35646925845.1092831772O(1)5015137754.4976693824130.5952627639.9812784952O(1)Table1 and Figure 3 show that the proposed upper bound Ub3 overcomes the upper bound UB0 and UB2 which is due to the works of Saha and Panigrahi [2] and Badr and Moussa [1], respectively. On the contrary, the proposed upper bound Ub3 overcomes the upper bound UB1 (for k is odd only) which is due to the works of Saha and Panigrahi [2]. The upper bound (for k is even) of the UB3 and UB1 are equal.Figure 3
Comparison among UB0, Ub1, UB2, and UB3 for the radio number of triangular snake.Table1 and Figure 4 explain that the proposed upper bounds outperform all results of UB0, UB1, and UB2 according to CPU time. On the contrary, the mathematical model UB2 [1] overcomes UB0 and UB1.Figure 4
Comparison among UB0, Ub1, UB2, and UB3 for the radio number of double triangular snake.


## 5. Conclusions

In this study, the upper bounds for the radio number of the triangular snake and the double triangular snake graphs are introduced. The computational results indicate that the presented upper bounds are better than the results of the mathematical model provided by Badr and Moussa [1]. On the contrary, these proposed upper bounds are better than the results of algorithms presented by Saha and Panigrahi [2, 3].



---

*Source: 3635499-2022-05-16.xml*