# Radio Labelings of Lexicographic Product of Some Graphs

Authors: Muhammad Shahbaz Aasi; Muhammad Asif; Tanveer Iqbal; Muhammad Ibrahim
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Labeling of graphs has defined many variations in the literature, e.g., graceful, harmonious, and radio labeling. Secrecy of data in data sciences and in information technology is very necessary as well as the accuracy of data transmission and different channel assignments is maintained. It enhances the graph terminologies for the computer programs. In this paper, we will discuss multidistance radio labeling used for channel assignment problems over wireless communication. A radio labeling is a one-to-one mapping℘:VG⟶ℤ+ satisfying the condition |℘μ−℘μ′|≥diamG+1−dμ,μ′:μ,μ′∈VG for any pair of vertices μ,μ′ in G. The span of labeling ℘ is the largest number that ℘ assigns to a vertex of a graph. Radio number of G, denoted by rnG, is the minimum span taken over all radio labelings of G. In this article, we will find relations for radio number and radio mean number of a lexicographic product for certain families of graphs.


---

## Body

## 1. Introduction

The notion of graph labeling was first introduced in 1966 by Rosa in [1], and since then, many different graph labelings have been defined and studied. In the 19th century, for studying the channel assignment problem, the term graph labeling was used where the transmitters are used as the vertices of the graph. Two vertices (transmitters) are said to be adjacent if they are sufficiently close to each other. A model of the channel assignment problem was provided by Hale [2] in 1980. Basic notions and definitions can be found in [3].LetG=VG,EG be a connected graph with vertex set VG and edge set EG. For any μ,μ′∈VG, let dμ,μ′ be the shortest length of the path between the vertices μ and μ′. A distance-two labeling is a function ℘:VG⟶1,2,3,…,k with span k having the maximum value k such that for any μ,μ′∈VG,μ≠μ′, the following relations are satisfied:(1)|℘μ−℘μ′|≥2,ifdμ,μ′=11,ifdμ,μ′=2.In 1992, Griggs and Yeh [4] extensively studied about distance-two labeling.An assignment of positive integers to the vertices ofG by ℘ of G is said to be a radio k-labeling if |℘μ−℘μ′|≥k+1−dμ,μ′, where k is an integer, k≥1. The span of labeling ℘, denoted by sp℘, is the max ℘μ−℘μ′:μ,μ′∈VG. Radio number of G, denoted by rnG, is the minimum span taken over all radio labelings of G. The radio k-labeling number of G is the minimum span among all radio k-labelings of G.The study of radiok-labelings was motivated by Chartrand et al. [5] where they found the radio k-labeling number for paths. In [5], the lower and upper bounds were given for the radio k-labeling number for paths which have been improved lately by Kchikech et al. [6]. The radio k-labeling becomes a radio labeling, when k=diamG. A radio labeling is a mapping from the vertices of the graph to some subsets of positive integers. The task of radio labeling is to assign to each station a positive smallest integer such that the interference in the nearest channel should be minimized. In 2001, multilevel distance labeling problem was introduced by Chartrand et al. [7].A radio labeling is a one-to-one mapping℘:VG⟶ℤ+ satisfying the condition(2)℘μ−℘μ′≥diamG+1−dμ,μ′:μ,μ′∈VG.In [8], multilevel distance (or radio) labeling for paths and cycles are determined by Liu and Zhu. Rahim et al. in [9] discussed and determined the radio number of Helm graphs. In [8], Liu et al. calculated the radio number of path graph. The radio numbers of hypercube graphs and square cycles have been computed by Khennoufa [10] and Liu et al. [11], respectively. In [12], Naseem et al. gave a lower bound for the radio number of edge-joint graphs. Adefokun and Ajayi [13] proved that for p≥4 and q even rnSp×Pq=pq2/2+q−1 and that for q even rnS3×Pq=3q2/2+q. Kim et al. [14] determined the radio numbers of Pq with q≥4 and Kp with p≥3. Lower bound has been improved by Bantva [15] for the radio number of graphs which was earlier given by Das et al. in [16]. For more results, we have [17–21].In [22], Ali et al. proposed a formula for finding a lower bound for rnG, for graphs with small diameter. It is sometimes very useful to determine how many pairs μs,μs+1 with ℘μs+1−℘μs=1 we can have. If there can be atmost ‘y’ such pairs in a graph G, then(3)rnG≥y+2q−1−y+1.In this paper, firstly, we determine the radio number and then radio mean number for the lexicographic product of path with path, path with cycle, and cycle with cycle. Finally, we present computer programs for finding such radio labelings of these families of graphs.


## 2. Applications

Labeling of graphs is one of the most popular parameters due to its diverse applications in real life. Radio labeling process proved as an efficient way of determining the time of communication for sensor networks. For giving valuable mathematical models, it has a wide scope of applications such as coding theory, electrical switchboards, circuit design, communication network addressing, channel assignment process, social networks, astronomy, demand and supply scenario, radar, database management, X-ray crystallography, and data security.


## 3. Lexicographic Product of Graphs

The lexicographic product was first studied by Hausdorff in 1914 [23]. The lexicographic product of two graphs G1 and G2 is denoted by G1G2 which is a graph with (Figure 1)(1)
The vertex set of the Cartesian productVG1×VG2, and(2)
Distinct verticesμ,μ′ and μ0,μ0′ are adjacent in G1G2 iff(a)
μμ0∈EG1, or(b)
μ=μ0 and μ′μ0′∈EG2.Figure 1
P4P3.


## 4. Main Results

In this section, we discuss the radio labelings and compute the radio number for the lexicographic product of path with pathPpPq and path with cycle PpCq for p=2,3. Moreover, we also presented a computer program for computing the radio number of these families of graphs.


### 4.1. Results of Radio Labeling

LetPq be the path with q vertices. The lexicographic product of P1 with Pq is isomorphic to graph Pq. The radio number of paths is investigated by Liu et al. in [8] as stated in the following result.Theorem 4.1 (see [8]).
For anyq≥3,(4)rnP1Pq=rnPq=2kk−1+1,ifq=2k,2k2+2,ifq=2k+1,. (5)rnP2Pq=2q,if q=1,2,2q+2,if q=3,2q+1,if q≥4,rnP2Cq=2q,if q=3,2q+3,if q=4,2q+1,if q≥5.We have a result for lower bound ofrnPpPq for p=2,3 and q≥4.Theorem 4.2.
For allq≥4, rnPpPq≥pq+1.Proof.
In order to prove that the value stated above is a lower bound for the radio number, we will use the idea of distance-two labeling, i.e., expression 1.
The order of the graphPpPq is pq for p=2,3 and there exists pq−2, such pairs with labeling difference equals to 1. So, 3 implies that(6)rnPpPq≥pq−2+2pq−1−pq−2=pq−2+2pq−1−pq+2+1=pq−2+2pq−2−2pq+4+1=pq+1,rnPpPq≥pq+1.Theorem 4.3.
For allq≥4, rnP2Pq≤2q+1.Proof.
The vertex set is partitioned in two disjoint setsVl and Vr. Each partition is given asVl=Vl1∪Vl2 and Vr=Vr1∪Vr2. For t=l,r, Vt1=vt1,vt2,vt3,…,vtq/2 and Vt2=vtq/2+1,vtq/2+2,vtq/2+3,…,vtq. Define a mapping ℘:VP2Pq⟶ℕ as follows:(7)℘vlq2−s+1=q+2sfors=1,2,3,…,q2℘vlq−s+1=q+1+2sfors=1,2,3,…,q−q2.℘vcq2−s+1=2s−1fors=1,2,3,…,q2℘vcq−s+1=2sfors=1,2,3,…,q−q2.℘vrq2−s+1=2q+sfors=1,2,3,…,q2℘vrq−s+1=2q+s+1fors=1,2,3,…,q−q2.Claim: the mapping℘ is a valid radio labeling. We must show that condition 2 for radio labeling holds for all pair of vertices μ,η∈VP2Pq.Case 1: supposeμ and η are any two vertices in Vl, then two subcases can be obtained.Case 1.1: letμ and η be any two distinct vertices in Vl1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=q+2k and. ℘η=q+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 1.2: letμ and η be any two distinct vertices in Vl2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=q+1+2k and ℘η=q+1+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2: suppose μ and η are any two vertices in Vc, then two subcases can be obtained.Case 2.1: letμ and η be any two distinct vertices in Vc1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=2k−1 and ℘η=2l−1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2.2: letμ and η be any two distinct vertices in Vc2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2k and ℘η=2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 3: supposeμ and η are any two vertices in Vr, then two subcases can be obtained.Case 3.1: letμ and η be any two distinct vertices in Vr1, then μ=vk and η=vl, 1≤k≠l≤q/2. therefore, ℘μ=2q+k and ℘η=2q+l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 3.2: letμ and η be any two distinct vertices in Vr2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2q+k+1 and ℘η=2q+l+1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Theorem 4.4.
(8)rnP3Pq=4,if q=1,3q+2,if q=2,3,3q+1,if q≥4,. (9)rnP3Cq=3q+1,ifq=3,3q+2,ifq=4,3q+1,ifq≥5,.Theorem 4.5.
For allq≥4, rnP3Pq≤3q+1.Proof.
The vertex set is partitioned in three disjoint setsVl,Vc, and Vr. Each partition is further partitioned in two disjoint sets, i.e., Vl=Vl1∪Vl2, Vc=Vc1∪Vc2 and Vr=Vr1∪Vr2. For t=l,c,r, Vt1=vt1,vt2,vt3,…,vtq/2 and Vt2=vtq/2+1,vtq/2+2,vtq/2+3,…,vtq. Define a mapping ℘:VP3Pq⟶ℕ as follows:(10)℘vlq/2−s+1=q+2sfors=1,2,3,…,q/2℘vlq−s+1=q+1+2sfors=1,2,3,…,q−q2.℘vcq2−s+1=2s−1fors=1,2,3,…,q2℘vcq−s+1=2sfors=1,2,3,…,q−q2.℘vrq/2−s+1=2q+sfors=1,2,3,…,q2℘vrq−s+1=2q+s+1fors=1,2,3,…,q−q2.Claim: the mapping℘ is a valid radio labeling. We must show that condition 2 for radio labeling holds for all pair of vertices μ,η∈VP3Pq.Case 1: supposeμ and η are any two vertices in Vl, then two subcases can be obtained.Case 1.1: letμ and η be any two distinct vertices in Vl1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=q+2k and ℘η=q+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 1.2: letμ and η be any two distinct vertices in Vl2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=q+1+2k and ℘η=q+1+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2: supposeμ and η are any two vertices in Vc, then two subcases can be obtained.Case 2.1: letμ and η be any two distinct vertices in Vc1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=2k−1 and ℘η=2l−1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2.2: letμ and η be any two distinct vertices in Vc2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2k and ℘η=2l. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+2k−l≥3.Case 3: supposeμ and η are any two vertices in Vr, then two subcases can be obtained.Case 3.1: letμ and η be any two distinct vertices in Vr1, then μ=vk and η==vl, 1≤k≠l≤q/2; therefore, ℘μ=2q+k and ℘η=2q+l. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+|2k−l|≥3.Case 3.2: letμ and η be any two distinct vertices in Vr2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2q+k+1 and ℘η=2q+l+1. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+2k−l≥3.


### 4.2. Computing Radio Number of Lexicographic Product of Graphs by Using Computer Language

This computer code has been composed by using Python language.import numpy as npimport math as mtdef main():m = int(input(‘m = Enter the number of vertices (either 2 or 3) = ‘))n = int(input(‘n = Enter the number of verticesn>=5  = ‘))name3 = input(‘Type rnPP for lexico of two path graphs, Type rnPC for radio number of path and cycles, Type exist to quit the program: ‘)while name3 ! = ‘exit’:if name3 = = ‘rnPP’:print(‘Executing rnPP’)rnpp(n, m)elif name3 = = ‘rnPC’:print(‘Executing rnPC’)rnpc(n, m)else:print(‘Input error: Enter the correct input value.‘)name3 = input(‘Enter rnPP for lexico of two path graphs, rnPC for radio number of path and cycles, or exist to quit the program: ‘)def rnpc(n, m):if m = = 2:q1 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)for i in range(0, q1, 1):l[q1-1-i] = 2∗ir[q1-1-i] = (n+1) + 2∗ifor j in range(1, n-q1+1, 1):l[n-j] = 2∗j-1r[n-j] = n+2∗jfor lc, rc in zip(l, r):print(lc, rc)elif m = = 3:q2 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)c = np.zeros(n, dtype = int)for i in range(0, q2, 1):l[q2-1-i] = (n+1) + 2∗ir[q2-1-i] = 2∗(n + i) + 1c[q2-1-i] = 2∗ifor j in range(1, n-q2+1, 1):l[n-j] = n + 2∗jr[n-j] = 2 ∗ (n + j)c[n-j] = 2 ∗ j-1for lc, cc, rc in zip(l, c, r):print(lc, cc, rc)else:print(‘Try again! Enter either 2 or 3 for the value of m.‘)exit()def rnpp(n, m):if m = = 2:q1 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)for i in range(0, q1, 1):l[q1-1-i] = 2∗i + 1r[q1-1-i] = (n+2) + 2∗ifor j in range(1, n-q1+1, 1):l[n-j] = 2∗jr[n-j] = (n+1) + 2∗jfor lc, rc in zip(l, r):print(lc, rc)elif m = = 3:q2 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)c = np.zeros(n, dtype = int)for i in range(0, q2, 1):l[q2-1-i] = (n+2) + 2∗ir[q2-1-i] = 2∗(n + i+1)c[q2-1-i] = 2∗i+1for j in range(1, n-q2+1, 1):l[n-j] = n + 2∗j+1r[n-j] = 2 ∗ (n + j) + 1c[n-j] = 2 ∗ jfor lc, cc, rc in zip(l, c, r):print(lc, cc, rc)else:print(‘Try again! Enter either 2 or 3 for the value of m.‘)exit()main()


## 4.1. Results of Radio Labeling

LetPq be the path with q vertices. The lexicographic product of P1 with Pq is isomorphic to graph Pq. The radio number of paths is investigated by Liu et al. in [8] as stated in the following result.Theorem 4.1 (see [8]).
For anyq≥3,(4)rnP1Pq=rnPq=2kk−1+1,ifq=2k,2k2+2,ifq=2k+1,. (5)rnP2Pq=2q,if q=1,2,2q+2,if q=3,2q+1,if q≥4,rnP2Cq=2q,if q=3,2q+3,if q=4,2q+1,if q≥5.We have a result for lower bound ofrnPpPq for p=2,3 and q≥4.Theorem 4.2.
For allq≥4, rnPpPq≥pq+1.Proof.
In order to prove that the value stated above is a lower bound for the radio number, we will use the idea of distance-two labeling, i.e., expression 1.
The order of the graphPpPq is pq for p=2,3 and there exists pq−2, such pairs with labeling difference equals to 1. So, 3 implies that(6)rnPpPq≥pq−2+2pq−1−pq−2=pq−2+2pq−1−pq+2+1=pq−2+2pq−2−2pq+4+1=pq+1,rnPpPq≥pq+1.Theorem 4.3.
For allq≥4, rnP2Pq≤2q+1.Proof.
The vertex set is partitioned in two disjoint setsVl and Vr. Each partition is given asVl=Vl1∪Vl2 and Vr=Vr1∪Vr2. For t=l,r, Vt1=vt1,vt2,vt3,…,vtq/2 and Vt2=vtq/2+1,vtq/2+2,vtq/2+3,…,vtq. Define a mapping ℘:VP2Pq⟶ℕ as follows:(7)℘vlq2−s+1=q+2sfors=1,2,3,…,q2℘vlq−s+1=q+1+2sfors=1,2,3,…,q−q2.℘vcq2−s+1=2s−1fors=1,2,3,…,q2℘vcq−s+1=2sfors=1,2,3,…,q−q2.℘vrq2−s+1=2q+sfors=1,2,3,…,q2℘vrq−s+1=2q+s+1fors=1,2,3,…,q−q2.Claim: the mapping℘ is a valid radio labeling. We must show that condition 2 for radio labeling holds for all pair of vertices μ,η∈VP2Pq.Case 1: supposeμ and η are any two vertices in Vl, then two subcases can be obtained.Case 1.1: letμ and η be any two distinct vertices in Vl1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=q+2k and. ℘η=q+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 1.2: letμ and η be any two distinct vertices in Vl2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=q+1+2k and ℘η=q+1+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2: suppose μ and η are any two vertices in Vc, then two subcases can be obtained.Case 2.1: letμ and η be any two distinct vertices in Vc1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=2k−1 and ℘η=2l−1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2.2: letμ and η be any two distinct vertices in Vc2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2k and ℘η=2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 3: supposeμ and η are any two vertices in Vr, then two subcases can be obtained.Case 3.1: letμ and η be any two distinct vertices in Vr1, then μ=vk and η=vl, 1≤k≠l≤q/2. therefore, ℘μ=2q+k and ℘η=2q+l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 3.2: letμ and η be any two distinct vertices in Vr2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2q+k+1 and ℘η=2q+l+1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Theorem 4.4.
(8)rnP3Pq=4,if q=1,3q+2,if q=2,3,3q+1,if q≥4,. (9)rnP3Cq=3q+1,ifq=3,3q+2,ifq=4,3q+1,ifq≥5,.Theorem 4.5.
For allq≥4, rnP3Pq≤3q+1.Proof.
The vertex set is partitioned in three disjoint setsVl,Vc, and Vr. Each partition is further partitioned in two disjoint sets, i.e., Vl=Vl1∪Vl2, Vc=Vc1∪Vc2 and Vr=Vr1∪Vr2. For t=l,c,r, Vt1=vt1,vt2,vt3,…,vtq/2 and Vt2=vtq/2+1,vtq/2+2,vtq/2+3,…,vtq. Define a mapping ℘:VP3Pq⟶ℕ as follows:(10)℘vlq/2−s+1=q+2sfors=1,2,3,…,q/2℘vlq−s+1=q+1+2sfors=1,2,3,…,q−q2.℘vcq2−s+1=2s−1fors=1,2,3,…,q2℘vcq−s+1=2sfors=1,2,3,…,q−q2.℘vrq/2−s+1=2q+sfors=1,2,3,…,q2℘vrq−s+1=2q+s+1fors=1,2,3,…,q−q2.Claim: the mapping℘ is a valid radio labeling. We must show that condition 2 for radio labeling holds for all pair of vertices μ,η∈VP3Pq.Case 1: supposeμ and η are any two vertices in Vl, then two subcases can be obtained.Case 1.1: letμ and η be any two distinct vertices in Vl1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=q+2k and ℘η=q+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 1.2: letμ and η be any two distinct vertices in Vl2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=q+1+2k and ℘η=q+1+2l. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2: supposeμ and η are any two vertices in Vc, then two subcases can be obtained.Case 2.1: letμ and η be any two distinct vertices in Vc1, then μ=vk and η=vl, 1≤k≠l≤q/2; therefore, ℘μ=2k−1 and ℘η=2l−1. Also, we note that dμ,η≥1; hence, dμ,η+|℘μ−℘η|≥1+2=3dμ,η+|2k−l|≥3.Case 2.2: letμ and η be any two distinct vertices in Vc2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2k and ℘η=2l. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+2k−l≥3.Case 3: supposeμ and η are any two vertices in Vr, then two subcases can be obtained.Case 3.1: letμ and η be any two distinct vertices in Vr1, then μ=vk and η==vl, 1≤k≠l≤q/2; therefore, ℘μ=2q+k and ℘η=2q+l. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+|2k−l|≥3.Case 3.2: letμ and η be any two distinct vertices in Vr2, then μ=vk and η=vl, 1≤k≠l≤q−q/2; therefore, ℘μ=2q+k+1 and ℘η=2q+l+1. Also, we note that dμ,η≥1; hence, dμ,η+℘μ−℘η≥1+2=3dμ,η+2k−l≥3.


## 4.2. Computing Radio Number of Lexicographic Product of Graphs by Using Computer Language

This computer code has been composed by using Python language.import numpy as npimport math as mtdef main():m = int(input(‘m = Enter the number of vertices (either 2 or 3) = ‘))n = int(input(‘n = Enter the number of verticesn>=5  = ‘))name3 = input(‘Type rnPP for lexico of two path graphs, Type rnPC for radio number of path and cycles, Type exist to quit the program: ‘)while name3 ! = ‘exit’:if name3 = = ‘rnPP’:print(‘Executing rnPP’)rnpp(n, m)elif name3 = = ‘rnPC’:print(‘Executing rnPC’)rnpc(n, m)else:print(‘Input error: Enter the correct input value.‘)name3 = input(‘Enter rnPP for lexico of two path graphs, rnPC for radio number of path and cycles, or exist to quit the program: ‘)def rnpc(n, m):if m = = 2:q1 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)for i in range(0, q1, 1):l[q1-1-i] = 2∗ir[q1-1-i] = (n+1) + 2∗ifor j in range(1, n-q1+1, 1):l[n-j] = 2∗j-1r[n-j] = n+2∗jfor lc, rc in zip(l, r):print(lc, rc)elif m = = 3:q2 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)c = np.zeros(n, dtype = int)for i in range(0, q2, 1):l[q2-1-i] = (n+1) + 2∗ir[q2-1-i] = 2∗(n + i) + 1c[q2-1-i] = 2∗ifor j in range(1, n-q2+1, 1):l[n-j] = n + 2∗jr[n-j] = 2 ∗ (n + j)c[n-j] = 2 ∗ j-1for lc, cc, rc in zip(l, c, r):print(lc, cc, rc)else:print(‘Try again! Enter either 2 or 3 for the value of m.‘)exit()def rnpp(n, m):if m = = 2:q1 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)for i in range(0, q1, 1):l[q1-1-i] = 2∗i + 1r[q1-1-i] = (n+2) + 2∗ifor j in range(1, n-q1+1, 1):l[n-j] = 2∗jr[n-j] = (n+1) + 2∗jfor lc, rc in zip(l, r):print(lc, rc)elif m = = 3:q2 = mt.ceil(n/2)l = np.zeros(n, dtype = int)r = np.zeros(n, dtype = int)c = np.zeros(n, dtype = int)for i in range(0, q2, 1):l[q2-1-i] = (n+2) + 2∗ir[q2-1-i] = 2∗(n + i+1)c[q2-1-i] = 2∗i+1for j in range(1, n-q2+1, 1):l[n-j] = n + 2∗j+1r[n-j] = 2 ∗ (n + j) + 1c[n-j] = 2 ∗ jfor lc, cc, rc in zip(l, c, r):print(lc, cc, rc)else:print(‘Try again! Enter either 2 or 3 for the value of m.‘)exit()main()


## 5. Results of Radio Mean Labeling

Ponraj et al. [24] discussed the radio mean labeling. In this section, we discuss the radio mean labeling and compute the radio mean number for the lexicographic product of path with path PpPq and path with cycle PpCq for p=2,3. Moreover, we also presented a computer program for computing the radio number of these families of graphs.Definition 5.1.
Radio mean labeling of a connected graphG is a one-to-one map ℘ from the vertex set VG to the set of natural numbers ℕ such that for two distinct vertices μ and μ′ of G,(11)dμ,μ′+℘μ+℘μ′2≥1+diamG.
The radio mean number of℘, denoted by rmn℘, is the maximum number assigned to any vertex of G. The radio mean number of G,rmnG is the minimum value of rmn℘ taken over all radio mean labeling ℘ of G.Theorem 5.2.
Forp=2,3 and q≥1, rmnPpPq=pq.Proof.
LetVPpPq=∪t=1pVts for p=2,3 and 1≤s≤q and EPpPq=vtivts+1:1≤t≤p;1≤s≤q∪vtsvt+1s′:1≤s,s′≤q. It is clear that diamPpPq=2. We define a vertex labeling ℘:VPpPq⟶ℕ as follows: ℘vts=ps−p+t for 1≤t≤p and 1≤s≤q. Now, we check the radio mean condition.(12)dμ,μ′+℘μ+℘μ′2≥1+diamPpPq,for all μ,μ′∈VPpPq.Case 1: the vertex labeling for the pairvts,vts+1 for a fixed t, 1≤t≤p and 1≤s≤q−1, is given as ℘vts=ps−p+t and ℘vts+1=ps+1−p+t=ps+t. Here, dvts,vts+1=1. So, dvts,vts+1+ps−p+t+ps+t/2=1+2ps−p+2j/2≥1+2≥3.Case 2: check the pairvts,vt+1s′ for a fixed t, 1≤t≤p−1 and 1≤s,s′≤q. ℘vts=ps−p+t, ℘vt+1s′=ps′−p+t+1, and dvts,vt+1s′=1. So, dvts,vt+1s′+ps−p+t+ps′−p+t+1/2=1+ps+s′−2+2t+1/2≥1+2≥3.Case 3: check the pairvts,vts′ for a fixed t, 1≤t≤p and s′=s+2, for 1≤s≤q−2. ℘vts=ps−p+t, ℘vts′=ps′−p+t, and dvts,vts′=2. So, dvts,vts′+ps−p+t+ps′−p+t/2=1+ps+s′−2p−t/2≥1+2≥3.


### 5.1. Computing Radio Mean Number of Lexicographic Product of Graphs by Using Computer Language

This computer code has been composed by using Python language.import numpy as npprint(‘Program to calculate the Radio Mean Labelling’)m = int(input(‘m = Enter the number of vertices (either 2 or 3) = ‘))n = int(input(‘n = Enter the number of verticesn>=1=′))if m = = 2:lt = np.zeros(n, dtype = int)rt = np.zeros(n, dtype = int)for j in range(1, m+1, 1):if j = = 1:for i in range(1, n+1, 1):lt[i-1] = m∗i - m + j.else:for i in range(1, n+1, 1):rt[i-1] = m∗i - m + j.for lc, rc in zip(lt, rt):print(lc, rc)elif m = = 3:lt = np.zeros(n, dtype = int)rt = np.zeros(n, dtype = int)ct = np.zeros(n, dtype = int)for j in range(1, m+1, 1):if j = = 1:for i in range(1, n+1, 1):lt[i-1] = m∗i - m + jelif j = = 2:for i in range(1, n+1, 1):ct[i-1] = m∗i - m + jelse:for i in range(1, n+1, 1):rt[i-1] = m∗i - m + jfor lc, cc, rc in zip(lt, ct, rt):print(lc, cc, rc)else:print(‘Error! The input value of m is either 2 or 3. Try again.‘)


## 5.1. Computing Radio Mean Number of Lexicographic Product of Graphs by Using Computer Language

This computer code has been composed by using Python language.import numpy as npprint(‘Program to calculate the Radio Mean Labelling’)m = int(input(‘m = Enter the number of vertices (either 2 or 3) = ‘))n = int(input(‘n = Enter the number of verticesn>=1=′))if m = = 2:lt = np.zeros(n, dtype = int)rt = np.zeros(n, dtype = int)for j in range(1, m+1, 1):if j = = 1:for i in range(1, n+1, 1):lt[i-1] = m∗i - m + j.else:for i in range(1, n+1, 1):rt[i-1] = m∗i - m + j.for lc, rc in zip(lt, rt):print(lc, rc)elif m = = 3:lt = np.zeros(n, dtype = int)rt = np.zeros(n, dtype = int)ct = np.zeros(n, dtype = int)for j in range(1, m+1, 1):if j = = 1:for i in range(1, n+1, 1):lt[i-1] = m∗i - m + jelif j = = 2:for i in range(1, n+1, 1):ct[i-1] = m∗i - m + jelse:for i in range(1, n+1, 1):rt[i-1] = m∗i - m + jfor lc, cc, rc in zip(lt, ct, rt):print(lc, cc, rc)else:print(‘Error! The input value of m is either 2 or 3. Try again.‘)


## 6. Conclusion

In this paper, we have discussed the radio number and radio mean number of lexicographic product of graphs, namely,P2Pq, P3Pq, P2Cq, and P3Cq for q≥5. We also computed the exact value of radio number and radio mean number of these families. Moreover, in this paper, we have presented their computer codes and also two open problems for future work have been given.


## 7. Open Problems

(1)
Determining the radio number ofPpPq for p≥4.(2)
Determining the radio mean number ofPpPq for p≥4.



---

*Source: 9177818-2021-12-07.xml*