A Novel Radio Geometric Mean Algorithm for a Graph

Abstract

Radio antennas switch signals in the form of radio waves using different frequency bands of the electromagnetic spectrum. To avoid interruption, each radio station is assigned a unique number. The channel assignment problem refers to this application. A radio geometric mean labeling of a connected graph $G$ is an injective function h from the vertex set, $V\left(G\right)$ to the set of natural numbers $N$ such that for any two distinct vertices $x$ and $y$ of $G$, $\sqrt{h\left(x\right)·h\left(y\right)}\ge diam+1-d\left(x,y\right)$. The radio geometric mean number of $h$, $rgmn\left(h\right)$, is the maximum number assigned to any vertex of $G$. The radio geometric mean number of G, $rgmn\left(G\right)$ is the minimum value of $rgmn\left(h\right)$, taken over all radio geometric mean labeling $h$ of $G$. In this paper, we present two theorems for calculating the exact radio geometric mean number of paths and cycles. We also present a novel algorithm for determining the upper bound for the radio geometric mean number of a given graph. We verify that the upper bounds obtained from this algorithm coincide with the exact value of the radio geometric mean number for paths, cycles, stars, and bi-stars.

1. Introduction

In all graphs, $\mathrm{G}=\left(\mathrm{V},\mathrm{E}\right)$ in this paper are finite, simple undirected, and connected graphs with $\mathrm{V}$ and $\mathrm{E}$ denoting the vertex set and edge set of $\mathrm{G}$, respectively. A graph labeling task is the task of assigning integers to vertices, edges, or both under certain conditions.

Graph labeling is used in a variety of sciences, including communication networks, coding theory, database administration, and so on. In particular, radio labeling is used to solve the channel assignment problem. For graph G, there are numerous types of radio labeling problems. The labeling of the vertices of a given graph G is done in such a way that the labels of any two vertices of G separated by d differ by at least $p_d$. The aim is to minimize the range (or span) of used frequencies, i.e., the difference between the smallest and the largest used label.

The channel assignment problem introduced by Hale [1] and in 2001 by Chartrand Erwin et al. [2] was motivated by regulations for channel assignments of FM radio stations to introduce radio labeling of graphs (multilevel distance labeling). Chartrand et al. [3] established the upper bounds for the radio numbers of cycles. Liu and Zhu [4] gave the exact value for the radio number of paths.

Compared to the others, Badr and Moussa [5] presented an improved upper bound for the radio $k$-chromatic number for a given graph. Saha and Panigrahi [6,7] investigated two radio k-coloring algorithms for general graphs, which will create radio k-colorings with their spans.

Ponraja et al. [8,9] defined the radio mean labeling of $G$ and proposed the radio mean number of graphs with a diameter of three, lotus inside a circle, Helms, and Sunflower graphs. Ponraja and Sathish [9] decided on the radio mean number of certain graphs, which are identified with complete bipartite graphs and cycles. In [10], the authors discovered the radio mean number of triangular ladder graph, $P_n☉{\overline{K}}_2$ ((it is made up of a path $P_n$ in which each vertex $x_i$ is connected to two vertices $y_i$ and $z_i$ of ${\overline{K}}_2)$, $K_n☉{\overline{K}}_2$ (consisting of a complete graph $K_n$ in which every vertex $x_i$ joins the two vertices $y_i$ and $z_i$ of ${\overline{K}}_2)$ and $W_n☉{\overline{K}}_2$ (consisting of a wheel $W_n$ in which every vertex $x_i$ joined the two vertices $y_i$ and $z_i$ of ${\overline{K}}_2)$. Kala [11] introduced the notion of radio mean labeling of graphs. The radio mean number of paths and cycles was discovered by Badr et al. [12]. In addition, they proposed an algorithm for determining the upper bounds of a graph’s radio-mean number and introduced a new mathematical model for the radio mean labeling application.

Ramesh et al. [13] examined the radio mean square labeling of graphs, like in the centric subdivision of spoke wheel graphs and bi-wheel graphs.

The radio geometric mean labeling of graphs was suggested by Hemalatha et al. [14] as follows:

(1)

A radio geometric mean labeling type of a connected graph $G$ is an injective function $h$ from the vertex set, $V$, to the set of natural numbers $N$, to achieve that for any two distinct vertices $u$ and $v$ in $V$, the value of $diam\left(G\right)+1-d\left(u,v\right)$ is always less than or equal to an integer number $Z=\lceil \sqrt{h\left(u\right)·h\left(v\right)}\rceil$, which is called a radio geometric mean labeling of $G$, where $d\left(u,v\right)$ denotes the distance between the two vertices $u$ and $v$ in $G$ and $diam\left(G\right)$ indicates the diameter of $G$. The study of paths and cycles s receives a lot of study and research, and it is of utmost importance in graph theory;

(2)

The authors discovered the radio geometric mean number of some star-like graphs.

The radio geometric mean number of some subdivision graphs was proposed by Hemalatha and Mohanaselvi [15], and in [16], the authors decided on the radio geometric mean number of shadowgraphs of the star and the bi-star.

For more details about the radio labeling, the reader can refer to [17,18,19]. On the other hand, for more details about the graph labeling, the reader is referred to [20,21,22,23,24,25].

The study of paths and cycles receives a lot of study and research and is of utmost importance in graph theory. There are many studies in terms of labeling, coloring, the study of topological indices, and other studies on the paths and cycles.

In the paper [26], the authors investigated the existence of the local super antenna magic total chromatic number for some particular classes of graphs, such as trees, paths, and cycles. In the paper [27], the authors give a characterization of the locating chromatic number of powers of paths. In addition, they find sharp upper and lower bounds for the locating chromatic number of powers of cycles. The main purpose of the paper [28] was to determine the crossing numbers of the join products of six symmetric graphs on six vertices with paths and cycles on n vertices. According to the paper [29], the exact value of the signed domination number for any positive integer is the Cartesian product of directed path and directed cycle.

In the paper [30], the authors obtain the g-extra connectivity of the strong products of two paths, a path and a cycle, and the strong product of two cycles. In addition, we mentioned earlier in many papers the study of radio on paths and cycles.

This paper studies the radio geometric mean number of paths and cycles and has proven that the radio geometric mean number of the path graph, $P_n$; where $n\ge 1,$ is given by:

$$rgmn\left(P_n\right)=\{\begin{array}{c}\begin{array}{c}n;\hspace{1em}if 1\le n\le 3\\ n+1;\hspace{1em}if n=4\end{array}\\ 2n-4;\hspace{1em}if n>4\end{array}$$

in addition we prove the radio geometric mean number of the cycle $C_n$, for $n\ge 3$ is given by:

$$rmsn\left(C_n\right)=\{\begin{array}{c}n\hspace{1em}if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor \hspace{1em}jf n\ge 6\end{array}$$

additionally, this paper introduces a novel approximate algorithm (Algorithm 1) that supplies an upper bound for the radio geometric mean number of a graph. Algorithm 1 is run on the paths and cycles to verify the proposed two theorems. Finally, Algorithm 1 is applied using the standard graphs of stars and bi-stars to compare the proposed Algorithm 1 against the related work [16].

The rest of this paper is structured as follows: radio geometric mean number of cycles and paths is presented with an example in Section 2, Section 3 proposes an approximate algorithm for determining the upper bound of the radio geometric mean number of a given graph, Section 4 contains an analysis of the results and a statistical test of the proposed approximate algorithm, and finally, in Section 5, conclusions are drawn.

2. Main Results

In this section, we introduce some basic definitions before we prove two theorems that determine the exact number of radio geometric means for paths and cycles.

Definition 1.

The distance from a vertex$u$to a vertex$v$is the number of edges in the shortest$u-v$path in$G,$and it is denoted by$d\left(u, v\right)$.

Definition 2.

The eccentricity$e\left(v\right)$of a vertex$v$in a connected graph$G$is the distance between$v$and the vertex farthest from$v$in$G$.

Definition 3.

The diameter$diam\left(G\right)$of$G$is the greatest eccentricity among the vertices of$G$.

Definition 4.

A radio geometric mean labeling is a one-to-one mapping$f$from$V\left(G\right)$to$N$satisfying the condition$\lceil \sqrt{h\left(x_i\right)h\left(x_j\right)}\rceil \ge diam\left(G\right)+1-d\left(x,y\right)$for every$x,u\in V\left(G\right)$. The radio geometric mean number of G is denoted by$rgmn\left(G\right)$.

2.1. Radio Geometric Means for Paths

Theorem 1.

The radio geometric mean number of the path graph $P_n$, where$n\ge 1,$is given by:

$$rgmn\left(P_n\right)=\{\begin{array}{c}\begin{array}{c}n; if 1\le n\le 3\\ n+1; if n=4\end{array}\\ 2n-4; if n>4\end{array}.$$

Proof. 

Let $u_1,u_2,\dots ,u_n$ be a path of length $n-1$, i.e., $diam\left(P_n\right)=n-1$. Define the function construct of the function. $h:V\left(P_n\right)\to N$, as the following:

Case a: For $1\le n\le 3$, we may label the vertices of $P_n$ as follows;

For $1\le n\le 3$, $P_n$’s vertices can be labeled as follows;

$h\left(u_1\right)=1, h\left(u_{n-i}\right)=2+i; 0\le i\le n-2$;

Case b: For $n=4$, we may label the vertices of $P_4$ as follows;

$h\left(u_1\right)=1, h\left(u_{i+2}\right)=5-i; 0\le i\le n-2$;

Case c: For $n\ge 5$, we may label the vertices of $P_n$ as follows;

$$\begin{array}{c}h\left(u_1\right)=n-3,\\ h\left(u_{n-i}\right)=n-2+i,\hspace{1em}0\le i<n-1\end{array}$$

therefore for almost any pair $\left(u_i,u_j\right), i\ne j, 1\le i,j\le n$, we have

$$d\left(u_i,u_j\right)+\lceil \sqrt{h\left(u_i\right)h\left(u_j\right)}\rceil \ge 1+\lceil \sqrt{\left(n-3\right)\left(2n-4\right)}\rceil \ge 1+n\ge 1+n-1=1+dim\left(P_n\right)$$

hence $h$ is a valid radio geometric mean labeling of $P_n$. Therefore, $rgmn\left(P_n\right)\le rgmn\left(h\right)=\{\begin{array}{c}n; if 1\le n\le 4\\ 2n-4; if n>4\end{array}$, since $h$ is injective, $rgmn\left(P_n\right)\ge \{\begin{array}{c}n; if 1\le n\le 4\\ 2n-4; if n>4\end{array}$ for all radio geometric mean labeling $h$ and hence $rgmn\left(P_n\right)=\{\begin{array}{c}n; if 1\le n\le 4\\ 2n-4; if n>4\end{array}$. One can easily see that the labeling $h:V\left(P_n\right)\to N$ defined above satisfies the radio geometric mean condition for $P_n$. □

Example 1.

The radio geometric mean numbers of$P_8, P_9, P_{96}$, and$P_{115}$are given in Figure 1.

2.2. Radio Geometric Means for Cycles

Theorem 2.

The radio geometric mean number of the cycle$C_n$, for$n\ge 3$is given by:

$$rmsn\left(C_n\right)=\{\begin{array}{c}n if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor jf n\ge 6\end{array}.$$

Proof. 

Let $x_1,x_2,\dots ,x_n$ be a cycle of length $n$, then $diam\left(C_n\right)=\lfloor \frac{n}{2}\rfloor$. Define the function $h:V\left(C_n\right)\to N$ as follows:

Case a: For $3\le n\le 5$, $C_n$’s vertices can be labeled as follows;

$h\left(x_i\right)=i; 1\le i\le n$;

Case b: For $n\ge 6$, we may label the vertices of $C_n$ as follows;

Case b.1:n is even;

$$\begin{array}{c}h\left(x_{\frac{n}{2}}\right)=1\\ h\left(x_{i+1}\right)=\lfloor \frac{n}{2}\rfloor +2i, 0\le i<\frac{n}{2}-1\\ h\left(x_{n-j}\right)=\lfloor \frac{n}{2}\rfloor -1+2j, 0\le j<\frac{n}{2}\end{array};$$

therefore for almost any pair $\left(x_i,x_j\right), i\ne j, 1\le i, j\le n$, we have

$$d\left(x_i,x_j\right)+\lceil \sqrt{h\left(x_i\right)h\left(x_j\right)}\rceil \ge 1+\lceil \sqrt{\left(\lfloor \frac{n}{2}\rfloor +2i\right)\left(\lfloor \frac{n}{2}\rfloor -1+2j\right)}\rceil \ge 1+\lfloor \frac{n}{2}\rfloor =1+dim\left(C_n\right)$$

Case b.2:n is odd;

$$\begin{array}{c}h\left(x_{\frac{n+1}{2}}\right)=1\\ h\left(x_{i+1}\right)=\lfloor \frac{n}{2}\rfloor +2i,\hspace{1em}0\le i<\frac{n-1}{2}\\ h\left(x_{n-j}\right)=\lfloor \frac{n}{2}\rfloor -1+2j,\hspace{1em}0\le j<\frac{n-1}{2}\end{array}$$

therefore for almost any pair $\left(x_i,x_j\right), i\ne j, 1\le i, \mathrm{and} j\le n$, we have

$$d\left(x_i,x_j\right)+\lceil \sqrt{h\left(x_i\right)h\left(x_j\right)}\rceil \ge 1+\lceil \sqrt{\left(\lfloor \frac{n}{2}\rfloor +2i\right)\left(\lfloor \frac{n}{2}\rfloor -1+2j\right)}\rceil 1+\lfloor \frac{n}{2}\rfloor =1+dim\left(C_n\right)$$

as a result, the radio geometric mean condition is met for all pairs of vertices. As a result, $h$ is a valid radio geometric mean labeling of $C_n$.

Therefore

$$rgmn\left(C_n \right)\le rgmn\left(h\right)\{\begin{array}{c}n if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor jf n\ge 6 \end{array}$$

(1)

since $h$ is injective,

$$rgmn\left(C_n\right)\ge \{\begin{array}{c}n\hspace{1em}\hspace{1em}\hspace{1em}if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor \hspace{1em}\hspace{1em}jf n\ge 6\end{array}$$

(2)

for all radio geometric mean labeling $h$ and hence

$$rgmn\left(C_n\right)=\{\begin{array}{c}n if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor jf n\ge 6 \end{array}$$

as a result, the labeling $h:V\left(C_n\right)\to N$ defined by the preceding cases meets the radio geometric mean condition. □

Example 2.

The radio geometric mean numbers of$C_8$,$C_9$,$C_{95}$, and $C_{112}$graphs are given in Figure 2.

3. A New Graph Radio Geometric Mean Algorithm

In this section, we propose an algorithm for calculating the upper bound of the radio geometric mean for any graph $G$. Integers are used to label all vertices. To begin, the diameter of the graph is given by the label of some vertex. Among the unlabeled vertices, a vertex is chosen that can be labeled with the fewest possible labels. The span is the label of the vertex, taken last in this order. By changing the initial vertex over the vertex set of the given graph, this algorithm is put to the test.

The Complexity of Algorithm 1: Step 3 is clearly the most expensive of the steps from 1 to 3. To compute Step 3, a nested double loop (one loop is $\left|S\right|$ times and the other is $\left|V\left(G\right)-S\right|$ times) is required. So, in the worst-case situation, the time complexity of Steps 1–3 is $O\left(n^2\right)$, where $n$ is the order of $G$. Steps 4 and 5 have an $O\left(n\right)$ time complexity, while Step 6 has an $O\left(1\right)$ time complexity. Step 7 has a time complexity of $O\left(n^3\right)$, and Step 8 has a time complexity of $O\left(n^4\right)$. As a result, the time complexity of Algorithm 1 is $O\left(n^4\right)$.

Algorithm 1. Finding an upper bound of the radio geometric mean number of a graph $G$.

Input: Let G be an $n$-vertex graph, a simple connected graph and the diameter of G (diam) be known;   Output: An upper bound of the radio geometric mean number of $G$;   Begin;   Step 1: Select a vertex $u$ and             $col\left(u\right)=\{\begin{array}{c}1, if diam=1,2\\ diam-2, if diam>2\end{array};$   Step 2: $S=\left\{u\right\}$;   Step 3: For all $v\in V\left(G\right)-S$, calculate,   $temp\left(v\right)=\underset{t\in s}{\max }\left\{\mathrm{ceil}\left(col\left(t\right)+\frac{\max \left\{\sqrt{(D+1-d\left(u,v\right),1}\right\}}{diam}\right)\right\}$;   Step 4: Let $\min =\underset{v\in V\left(G\right)-S}{\min }\left\{temp\left(v\right)\right\}$;   Step 5: Select a vertex $v\in V\left(G\right)-S$. Such that $temp\left(v\right)=min$;   Step 6: Give $col\left(v\right)=min$;   Step 7: $S=S\cup \left\{v\right\}$;   Step 8: Steps 3–6 should be repeated until all the vertexes are labeled;   Step 9: Steps 1–7 should be repeated for each $x\in V\left(G\right)$;   End.

Example 3.

(Algorithm 1 for P₅).

We show how to solve the radio geometric mean labeling problem using the path graph $P_5$. Assume that $x_i$ are the labels of the vertices $v_i$ in such a way that $1\le i\le 5$. As a result, Algorithm 1 computes an upper bound for the radio geometric mean labeling problem as follows:

It is known that $diam\left({\mathrm{P}}_5\right)=4$. We choose a vertex $x_1$ and $col\left(x_1\right)=2$. Let $\mathrm{S}=\left\{x_1\right\}$ and for every $v\in V\left(G\right)-S$, calculate,

$$temp\left(x_2\right)=\underset{x_1}{\max }\left\{2+\mathrm{ceil}\left(\frac{\max \left\{(\sqrt{5-1},1\right\}}{4}\right)\right\}=3$$

$$temp\left(x_3\right)=\underset{x_1}{\max }\left\{2+\mathrm{ceil}\left(\frac{\max \left\{(\sqrt{5-2},1\right\}}{4}\right)\right\}=3$$

$$temp\left(x_4\right)=\underset{x_1}{\max }\left\{2+\mathrm{ceil}\left(\frac{\max \left\{(\sqrt{5-3},1\right\}}{4}\right)\right\}=3$$

$$temp\left(x_5\right)=\underset{x_1}{\max }\left\{2+\mathrm{ceil}\left(\frac{\max \left\{(\sqrt{5-4},1\right\}}{4}\right)\right\}=3$$

let $\min =\underset{v\in V\left(G\right)-S}{\min }\left\{temp\left(v\right)\right\}=3$. We choose a vertex $x_2\in V\left(G\right)-S.$ Such that $temp\left(x_2\right)=3$. Give $col\left(x_2\right)=3$ and $S=\left\{x_1,x_2\right\}$

$$temp\left(x_3\right)=\underset{\{x_1,x_2\}}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-2},1\right\}}{4}\right)\\ 3+ceil\left(\frac{max\left\{(\sqrt{5-1},1\right\}}{4}\right)\end{array}\right\}=4$$

$$temp\left(x_4\right)=\underset{\{x_1,x_2\}}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-3},1\right\}}{4}\right)\\ 3+ceil\left(\frac{max\left\{(\sqrt{5-2},1\right\}}{4}\right)\end{array}\right\}=4$$

$$temp\left(x_5\right)=\underset{\{x_1,x_2\}}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-4},1\right\}}{4}\right)\\ 3+ceil\left(\frac{max\left\{(\sqrt{5-3},1\right\}}{4}\right)\end{array}\right\}=4$$

let $\min =\underset{v\in V\left(G\right)-S}{\min }\left\{temp\left(v\right)\right\}=4$. We choose a vertex $x_3\in V\left(G\right)-S,$ where $temp\left(x_3\right)=4$. Give $col\left(x_3\right)=4$ and $S=\left\{x_1,x_2,x_3\right\}$

$$temp\left(x_4\right)=\underset{\left\{x_1,x_2,x_3\right\}}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-3},1\right\}}{4}\right)\\ 3+ceil\left(\frac{max\left\{(\sqrt{5-2},1\right\}}{4}\right)\\ 4+ceil\left(\frac{max\left\{(\sqrt{5-1},1\right\}}{4}\right)\end{array}\right\}=5$$

$$temp\left(x_5\right)=\underset{\left\{x_1,x_2,x_3\right\}}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-4},1\right\}}{4}\right)\\ 3+ceil\left(\frac{max\left\{(\sqrt{5-3},1\right\}}{4}\right)\\ 4+ceil\left(\frac{max\left\{(\sqrt{5-2},1\right\}}{4}\right)\end{array}\right\}=5$$

let $\min =\underset{v\in V\left(G\right)-S}{\min }\left\{temp\left(v\right)\right\}=5,$ we choose a vertex $x_4\in V\left(G\right)-S,$ where $temp\left(x_4\right)=5$. Give $col\left(x_4\right)=5$ and $S=\left\{x_1,x_2,x_3,x_4\right\}$

$$temp\left(x_5\right)=\underset{x_1}{max}\left\{\begin{array}{c}2+ceil\left(\frac{max\left\{(\sqrt{5-4},1\right\}}{4}\right)\\ \begin{array}{c}3+ceil\left(\frac{max\left\{(\sqrt{5-3},1\right\}}{4}\right)\\ 4+ceil\left(\frac{max\left\{(\sqrt{5-2},1\right\}}{4}\right)\end{array}\\ 5+ceil\left(\frac{max\left\{(\sqrt{5-1},1\right\}}{4}\right)\end{array}\right\}=6$$

let $\min =\underset{v\in V\left(G\right)-S}{\min }\left\{temp\left(v\right)\right\}=6$. We select a vertex $x_5\in V\left(G\right)-S$, such that $temp\left(x_5\right)=6$. Give $col\left(x_5\right)=6$ and $S=\left\{x_1,x_2,x_3,x_4,x_5\right\}$. All vertices are clearly labeled, and $rgmn\left(P_5\right)=6$.

4. Discussion

The computing environment is described in

Table 1. Description of the computing environment.

CPU	Intel (R) Core (TM) i5-2430U [email protected] GHz)
RAM Size	4 GB RAM
MATLAB version	R2018a (9.4.0.813654)

. To solve Algorithm 1, we use the MATLAB R2018a solver. This paper describes an analysis of the results and a statistical test of the proposed approximate algorithm in this section and presents the computational results in

Table 2. A comparison between Algorithm 1 and Theorems 1 and 2 for paths and cycles.

Paths				Cycles
n	Standard RGM	Proposed Algorithm		Standard RGM	Proposed Algorithm
		rgmn(Pn)	CPU Time		rgmn(Cn)	CPU Time
1	1	-	-	-	-	-
2	2	2	0.006218	-	-	-
3	3	3	0.002032	3	3	0.0002965
4	5	5	0.000326	4	4	0.0004289
5	6	6	0.001283	5	5	0.0007612
6	8	8	0.001961	6	6	0.001869
7	10	10	0.00403	7	7	0.003384
8	12	12	0.007533	9	9	0.003956
9	14	14	0.008089	10	10	0.005045
10	16	16	0.013975	12	12	0.006979
11	18	18	0.01105	13	13	0.009726
12	20	20	0.015964	15	15	0.016311
13	22	22	0.016252	16	16	0.020546
14	24	24	0.020594	18	18	0.042627
15	26	26	0.039209	19	19	0.04193
16	28	28	0.043435	21	21	0.044663
17	30	30	0.060237	22	22	0.062776
18	32	32	0.053166	24	24	0.0729
19	34	34	0.065707	25	25	0.102526
20	36	36	0.080248	27	27	0.108967
21	38	38	0.097369	28	28	0.146018
22	40	40	0.11666	30	30	0.126386
23	42	42	0.138594	31	31	0.155682
24	44	44	0.173809	33	33	0.18924
25	46	46	0.193142	34	34	0.212628
26	48	48	0.225838	36	36	0.368085
27	50	50	0.258798	37	37	0.449963
28	52	52	0.302328	39	39	0.589237
29	54	54	0.345496	40	40	0.654655
30	56	56	0.400023	42	42	0.839791
50	96	96	3.5304817	72	72	2.8864912

. Algorithm 1 is tested on paths, cycles, stars, and bi-stars.

Definition 5.

A star is the complete bipartite graph$K_{1,n}$.

Definition 6.

The graph obtained by connecting the center (apex) vertices of two copies of$K_{1,n}$by an edge is known as a bi-star$B_{n,n}$. The vertex set of $B_{n,n}$is$V\left(B_{n,n}\right)=\left\{u,v,u_i,v_i/1\le i\le n\right\}$, where $u and v$are apex vertices and $u_i and v_i$are pendant vertices. The edge set of $B_{n,n}$is$E\left(B_{n,n}\right)=\left\{uv,u{u}_i,v{v}_i/1\le i\le n\right\}$. So, $\left|V\left(B_{n,n}\right)\right|=2n+2$and$\left|E\left(B_{n,n}\right)\right|=2n+1$.

The abbreviations Standard RGMN, computed $rgmn\left(G\right)$ and CPU Time are used in Table 2 and

Table 3. A comparison between Algorithm 1 and the results in references [15,16] for stars and bi-stars.

Stars					Bistars
n	Number of Vertices	Standard RGM	Proposed Algorithm		Number of Vertices	Standard RGM	Proposed Algorithm
			$\mathit{r}\mathit{g}\mathit{m}\mathit{n}\left({\mathit{S}}_{\mathit{n}}\right)$	CPU Time			$\mathit{r}\mathit{g}\mathit{m}\mathit{n}\left({\mathit{B}}_{\mathit{n},\mathit{n}}\right)$	CPU Time
1	2	2	2	0.0020687	4	5	5	0.0029455
2	3	3	3	0.0030152	6	6	6	0.0050051
3	4	4	4	0.0030554	8	8	8	0.0077476
4	5	5	5	0.0031072	10	10	10	0.0162649
5	6	6	6	0.0047009	12	12	12	0.0270769
6	7	7	7	0.005181	14	14	14	0.0344096
7	8	8	8	0.005945	16	16	16	0.0639565
8	9	9	9	0.0076537	18	18	18	0.0851445
9	10	10	10	0.0099313	20	20	20	0.1094354
10	11	11	11	0.020052	22	22	22	0.1426846
11	12	12	12	0.0255199	24	24	24	0.1986474
12	13	13	13	0.0331355	26	26	26	0.2558788
13	14	14	14	0.0358719	28	28	28	0.3395264
14	15	15	15	0.0565693	30	30	30	0.4030834
15	16	16	16	0.0688593	32	32	32	0.4804848
16	17	17	17	0.0876509	34	34	34	0.6043567
17	18	18	18	0.0940411	36	36	36	0.7527568
18	19	19	19	0.1133618	38	38	38	0.9098608
19	20	20	20	0.1243284	40	40	40	1.0976991
20	21	21	21	0.1514262	42	42	42	1.3303740
21	22	22	22	0.1617064	44	44	44	1.5555509
22	23	23	23	0.1791063	46	46	46	1.8556716
23	24	24	24	0.1936942	48	48	48	2.1834102
24	25	25	25	0.2197022	50	50	50	2.5481004
25	26	26	26	0.2436268	52	52	52	2.9699905
26	27	27	27	0.2750292	54	54	54	3.7919474
27	28	28	28	0.3269645	56	56	56	4.1813628
28	29	29	29	0.352134	58	58	58	4.9736259
29	30	30	30	0.4196667	60	60	60	5.5554632
30	31	31	31	0.4664257	62	62	62	6.7576094
50	51	51	51	2.8473028	102	102	102	56.809173

to denote the exact and computed radio geometric mean numbers, as well as the running times for paths, cycles, stars, and bi-stars, respectively.

Table 2 shows that the upper bound obtained from the proposed Algorithm 1 coincides with the exact value of the radio geometric mean number. The exact values of RGMN were obtained from Theorem 1 (paths) and Theorem 2 (cycles). On the other hand, we evaluate Algorithm 1 with benchmark graphs, stars, and bi-stars [14,15,16].

Table 3 shows that the upper bound obtained from the proposed Algorithm 1 coincides with the exact value of the radio geometric mean number. These exact values of RGMN were obtained from the references [14,15,16] for stars and bi-stars.

From Table 2 and Table 3, we note that as the number of vertices increases, the running time increases.

Figure 3 and Figure 4 illustrate the RGM and CPU time for paths, cycles, stars graphs, and bi-stars graphs, respectively.

Remark 1.

From Table 2 and Table 3, we note that the values of CPU time are positive real numbers and are too close to each other. For this reason, in Figure 4, we plot the logarithm of CPU time instead of CPU time.

5. Conclusions

In this work, we propose two theorems that determine the exact radio geometric mean number (RGMN) for paths and cycles.

Theorem 3.

The radio geometric mean number of the path graph$P_n$, where $n\ge 1,$is given by:

$$rgmn\left(P_n\right)=\left\{\begin{array}{c}n; if 1\le n\le 3\\ n+1; if n=4\\ 2n-4; if n>4\end{array}\right..$$

Theorem 4.

The radio geometric mean number of the cycle$C_n$, for $n\ge 3$is given by:

$$rmsn\left(C_n\right)=\left\{\begin{array}{c}n\hspace{1em}if 3\le n\le 5\\ \lfloor \frac{3n}{2}-3\rfloor \hspace{1em}jf n\ge 6\end{array}\right..$$

We also introduced a novel algorithm that finds an upper bound for the RGMN of a given graph. We checked that for paths, cycles, stars, and bi-stars, the upper bounds obtained from this algorithm coincide with the exact value of the radio geometric mean number. We deduced that building radio stations is analogous to building stars. In the future, we will apply Algorithm 1 to other graphs to recommend how radio stations can be built.