Bounds on radio mean number of graphs

Abstract

A radio mean labeling l of G maps distinct vertices of G to distinct elements of $ℤ^{+}$ satisfying the radio mean condition that $diam (G) + 1 - d_{G} (w, w^{'}) \leq ⌈ \frac{l (w) + l (w^{'})}{2} ⌉, \forall w, w^{'} \in V (G)$ where d_G (w, w′) is the smallest length of a w, w′- path in G and diam (G) = max {d_G (w, w′) : w, w′ ∈ V (G)} is the diameter of G. The radio mean number of graph G is defined as rmn (G) = min {span (l) : l isaradiomeanlabelingof G} where span(l) is given by max {l (w) : w ∈ V (G)}. It has been proved in literature that |V (G) | ≤ rmn (G) ≤ |V (G) | + diam (G) -2. Cryptographic algorithms can exploit the unique radio mean number associated with a graph to generate keys. An exhaustive listing of all feasible radio mean labelings and their span is essential to obtain the radio mean number of a given graph. Since the radio mean condition depends on the distance between vertices and the graph’s diameter, as the order and diameter increase, finding a radio mean labeling itself is quite difficult and, so is obtaining the radio mean number of a given graph. Here we discuss the extreme values of the radio mean number of a given graph of order n. In this article we obtained bounds on the radio mean number of a graph G of order n and diameter d in terms of the radio mean number of its induced subgraph H where diam (H) = d and d_H (w, w′) = d_G (w, w′) for any w, w′ ∈ V (H). The diametral path P_d+1 is one such induced subgraph of G and hence we have deduced the limits of rmn (G) in terms of rmn (P_d+1). It is known that if d = 1, 2 or 3, then rmn (G) = n. Here, we have given alternative proof for the same. The authors of this article have studied radio mean labeling of paths in another article. Using those results, we have improved the bounds on the radio mean number of a graph of order n and diameter d ≥ 4. It is also shown that among all connected graphs on n vertices, the path P_n of order n possesses the maximum radio mean number. This is the first article that has completely solved the question of maximum and minimum attainable radio mean numbers of graphs of order n.

Keywords

Channel assignment problem graph labeling radio labeling radio mean labeling radio mean number paths

1 Introduction

Graph theory studies graphs, mathematical models of objects(represented as vertices), and their relations(represented as edges). Many real-life scenarios can be conveniently modeled and studied using graphs. For example, graphs are used to model chemical molecules, geographic adjacency, activity scheduling problems, personnel-assignment problems, interconnection networks for parallel architectures, acquaintance networks, radio channel assignment problems, and so on [8]. In this 21st century, “Social networks” play an essential role in man’s life. Graphs can be used to detect communities within a social network. Centrality measures of a graph(network) identify its critical nodes(people) [6]. In situations where the relationships between objects are unclear or fuzzy, fuzzy graph models are more suitable. For example, the idea of fuzzy graphs is used to model the order of journeys from one place to another [17], communication system between teachers and students for the improvement of teaching [18], and connection of Wi-Fi network in a town [19], social network group with communication gaps [20], and so on. To identify the most affected COVID-19 cycles between some communicated countries [21], the concept of fuzzy graphs can be exploited. There are many active research areas in graph theory. One among them is the labeling of graphs. This article deals with the graph labeling technique called radio mean labeling.

1.1 Research background

For basic definitions and concepts in Graph theory, we refer [27]. Note that the graphs considered in this study are simple and connected. There are many graph coloring and labeling techniques proposed in connection with the Channel assignment problem of assigning channels optimally. It can be modeled as a distance-constrained labeling of graphs. One such graph labeling technique is radio labeling, defined by Gary Chartrand and others in [5] as a mapping of vertices of the graph G to $ℤ^{+}$ satisfying the condition that ∀w, w′ ∈ V (G), $diam (G) + 1 - d (w, w^{'}) \leq | l (w) - l (w^{'}) |,$ where d (w, w′) is the smallest length of a w, w′- path in G and $diam (G) = max_{w, w^{'} \in V (G)} d (w, w^{'})$ is the diameter of G. The radio number of G is given by rn (G) = min {span (l) : l isaradiolabeling of G} where span (l) is given by max {l (w) : w ∈ V (G)}. In [10], D.Liu and X.Zhu have obtained the radio number of path P_m, m ≥ 3 as $rn (P_{m}) = {\begin{matrix} 2 l^{2} + 3 & if m = 2 l + 1 \\ 2 (l^{2} - l + 1) & if m = 2 l \end{matrix}$ Different radio labelings of path P₅ are shown in Fig.1. The span of radio labelings in Fig.1 are 15, 13, 12, and 11 respectively and the radio number of P₅ is 11.

Fig. 1

Different radio labelings of P₅.

Radio mean labeling is a modified form of radio labeling and is defined by R.Ponraj et al. in [12] as follows: A radio mean labeling l of G maps distinct vertices of G to distinct elements of $ℤ^{+}$ satisfying the radio mean condition that ∀w, w′ ∈ V (G) $diam (G) + 1 - d (w, w^{'}) \leq ⌈ \frac{l (w) + l (w^{'})}{2} ⌉ .$ The radio mean number of graph G is given by rmn (G) = min {span (l) : l is a radio mean labeling of G} where span (l) is given by max {l (w) : w ∈ V (G)}. Authors of [9] called a graph with radio mean number the same as its order as radio mean graceful graph.

Consider the path P₅ whose diameter is 4. Assume that a radio mean labeling of P₅ exists with a span equal to 5. Then, its range is {1, 2, 3, 4, 5}. Let u₁, u₂, u₃, u₄, u₅ be an arrangement of vertices of P₅ in the increasing order of vertex labels. Then u_i ⟼ i, 1 ≤ i ≤ 5. To satisfy the radio mean condition, d_{P
₅} (u₁, u₂) must be at least 3, d_{P
₅} (u₁, u₃) must be at least 3 and d_{P
₅} (u₂, u₃) must be at least 2. These constraints make the labeling impracticable. Thus there exists no radio mean labeling of P₅ with integers in {1, 2, 3, 4, 5} as labels and hence rmn (P₅) >5. Different radio mean labelings of path P₅ are shown in Fig.2. The span of radio mean labelings in Fig.2 are 7, 7, 7, and 6 respectively. Among all radio mean labelings of P₅, the least span is 6 and so rmn (P₅) =6.

Fig. 2

Different radio mean labelings of P₅.

1.2 Literature review

Determining the radio mean number of graphs is quite difficult, and it is determined for only a handful of classes of graphs. In [12] the radio mean labeling of graphs with a diameter of either two or three, sunflower graphs, lotus inside a circle, gear graphs, and helm graphs are studied. Ponraj et al. obtained the radio mean numbers of the subdivision graph of complete bipartite graphs, corona product of complete bipartite graph with path, and the friendship graph in [13] and that of the subdivision graphs of star, wheel, bistar, and K₂ + mK₁ in [15]. In [14] Ponraj et al. obtained the radio mean numbers of the corona of wheel W_n with path P_m, the graph W_m,n which is formed by joining the vertices other than the hub of the two wheels, say W_m and W_n with an edge, and the graph sp (W_n) which is formed by subdividing each of the spokes of the wheel graph W_n. Ponraj and Satish determined the radio mean numbers of jelly fish and its subdivision graph, book with n pentagonal pages, and the graph <K_1,n : m> obtained by joining a new vertex to the centers of the m disjoint copies of K_1,n in [16]. In [26], Sunitha et al. determined the radio mean number of triangular ladder graph, corona P_n with $\bar{K_{2}}$ , corona K_n with $\bar{K_{2}}$ and corona W_n with $\bar{K_{2}}$ . In [9] Lavanya and Meera provided the radio mean number of subdivision of complete graphs, mangolian tent graph, subdivision of friendship graphs, and diamond graphs. The article [25] discusses the radio mean labeling of cycles. In [22], the authors have obtained the radio mean numbers of the path and the total graph of path. In [11], the author discusses radio geometric mean labeling of graphs. Authors study total edge product cordial labeling in [1 –3], and [4]. The articles [23] and [24] discuss applications of radio mean labeling technique in cryptography.

1.3 Motivation of this study

In Fig. 2, we have seen four different radio mean labelings of path P₅. It is to be noted that these are not the only feasible radio mean labelings of P₅. The radio mean condition completely depends on the distance between vertices and the graph’s diameter. As the order and diameter increase, finding all possible labelings satisfying the radio mean condition for any given graph is challenging. An exhaustive listing of all feasible radio mean labelings and their span is essential to obtain radio mean number of a given graph. In [12] R.Ponraj et al. observed that if the diameter of G is either 2 or 3, then rmn (G) = |V (G) |. It is given in [12] that for any graph G, |V (G) | ≤ rmn (G) ≤ |V (G) | + diam (G) -2. In this paper, we attempt to find sharper bounds on the radio mean number of a graph on n vertices and diameter d than the ones obtained in [12].

1.4 Framework of this study

In section 2.1, we obtained bounds on the radio mean number of a graph in terms of the radio mean number of its induced subgraph under certain conditions. Later in section 2.2, we use the results on radio mean labeling of paths with minimum span obtained in paper [22] to improve the bounds on the radio mean number of a graph in terms of its order and diameter. It is also shown that among all graphs on n vertices, the path P_n possesses the maximum radio mean number. In section 2.3, we show with an example the upper bound of the radio mean number obtained in section 2.2 is much less than the bound mentioned in [12]. In section 3, we explain the applications of this labeling technique in cryptography. Finally, we conclude the article in section 4 by summarizing all key results we obtained and posing some open problems.

2 Bounds on radio mean number of graphs

Suppose that G is a graph on n vertices with diameter d. When K ⊆ V (G), the induced subgraph $H = G [K] = G - \bar{K}$ . In this section, first, we obtain bounds for the radio mean number of G in terms of the radio mean number of H. The second section gives bounds on radio mean number in terms of n and d.

2.1 Bounds on radio mean number of graph G in terms of the radio mean number of an induced subgraph of G

Theorem 1.Let H be an induced subgraph of order p of a graph G of order n. Suppose that diam (G) = diam (H) = d and the length of the shortest path between any two distinct vertices in H is the same as that in G. Then $rmn (H) \leq rmn (G) \leq rmn (H) + 2 d (n - p) .$

Proof. If p = n, then H = G and rmn (H) = rmn (G). Now assume that H is an induced subgraph of G with V (H) ⊂ V (G) and E (H) ⊂ E (G) where V (G) = {v₁, v₂, ⋯ , v_n} and V (H) = {v₁, v₂, ⋯ , v_p} , p < n. We claim that restriction of any radio mean labeling Γ of G on V (H) is a radio mean labeling of H. Let us denote Γ|_V(H) by γ. Γ maps distinct integers to distinct vertices and so does γ. Also, for (v_i, v_j) ∈ V (H) $\begin{matrix} ⌈ \frac{γ (v_{i}) + γ (v_{j})}{2} ⌉ + d_{H} (v_{i}, v_{j}) & = & ⌈ \frac{Γ (v_{i}) + Γ (v_{j})}{2} ⌉ \\ + & d_{G} (v_{i}, v_{j}) \geq d + 1 . \end{matrix}$

Thus γ is a radio mean labeling of graph H with the span of γ ≤ span of Γ. Since Γ is chosen arbitrarily, it also holds good with a radio mean labeling with a minimum span of G. Hence, span of γ ≤ rmn (G). Again by the definition of radio mean number, we have rmn (H) ≤ rmn (G).

Now let γ be any arbitrary radio mean labeling of H whose span is r and range set be denoted by $R (γ)$ . Then for every pair of distinct vertices v_i, v_j of H,

$⌈ \frac{γ (v_{i}) + γ (v_{j})}{2} ⌉ + d_{H} (v_{i}, v_{j}) \geq d + 1 .$

Define Γ on V (G) by $Γ (v) = {\begin{matrix} γ (v) : v \in V (H) \\ k : otherwise \end{matrix}$ where k ∈ {r + 2d (i - p) : i = p + 1, p + 2 ⋯ , n} and Γ (v) ≠ Γ (u) if v ≠ u. Clearly, $Γ : V (G) ⟶ R (γ) ⋃ {r + 2 d (i - p) : p + 1 \leq i \leq n}$ maps distinct integers to distinct vertices.

We claim that Γ satisfies radio mean condition. Let (u₁, u₂, ⋯ , u_n) be an arrangement of elements of V (G) such that Γ (u_i) < Γ (u_j) , 1 ≤ i < j ≤ n. Note that in this ordering, vertices u₁, u₂, ⋯ , u_p belong to V (H), and the remaining vertices u_p+1, u_p+2, ⋯ , u_n belong to V (G) \ V (H). Consider u_l, u_m ∈ V (G) where 1 ≤ l ≤ p, p + 1 ≤ m ≤ n . $\begin{matrix} ⌈ \frac{Γ (u_{l}) + Γ (u_{m})}{2} ⌉ + d_{G} (u_{l}, u_{m}) & = & ⌈ \frac{γ (u_{l}) + r}{2} + \\ d (m - p) ⌉ + \\ d_{G} (u_{l}, u_{m}) \\ = & ⌈ \frac{γ (u_{l}) + γ (u_{p})}{2} + \\ d (m - p) ⌉ + \\ d_{G} (u_{l}, u_{m}) \\ \geq & ⌈ \frac{γ (u_{l}) + γ (u_{p})}{2} ⌉ \\ + ⌈ \frac{2 d (m - p)}{2} ⌉ \\ - 1 + d_{G} (u_{l}, u_{m}) \\ \geq & d + 1 - d_{H} (u_{l}, u_{p}) \\ + d (m - p) - 1 \\ + d_{G} (u_{l}, u_{m}) \\ \geq & d + 1 . \end{matrix}$ Consider u_l, u_m ∈ V (G) where 1 ≤ l, m ≤ p, l ≠ m. $\begin{matrix} ⌈ \frac{Γ (u_{l}) + Γ (u_{m})}{2} ⌉ + d_{G} (u_{l}, u_{m}) & = & ⌈ \frac{γ (u_{l}) + γ (u_{m})}{2} ⌉ \\ + d_{H} (u_{l}, u_{m}) \\ \geq & d + 1 . \end{matrix}$ Consider u_l, u_m ∈ V (G) where p + 1 ≤ l, m ≤ n, l ≠ m . size9.211.2 $\begin{matrix} ⌈ \frac{Γ (u_{l}) + Γ (u_{m})}{2} ⌉ + d_{G} (u_{l}, u_{m}) & = & ⌈ r + d (l + m - 2 p) ⌉ \\ + d_{G} (u_{l}, u_{m}) \\ \geq & d + 1 . \end{matrix}$

Hence Γ is a radio mean labeling of G with span r + 2d (n - p). So we have rmn (G) ≤ span (γ) +2d (n - p) . Since γ is chosen arbitrarily, this inequality also holds good if γ is a radio mean labeling with minimum span. Hence rmn (H) ≤ rmn (G) ≤ rmn (H) +2d (n - p).□

Let us illustrate the idea of the theorem 2.1 with an example. Let G be the cycle C₈ : v₁v₂ ⋯ v₈ and H be the path P₅ : v₁v₂v₃v₄v₅ which is an induced subgraph of C₈ with properties specified in the 2.1 Theorem1. Let us first show that rmn (G) is always greater than or equal to rmn (H). Figure 3 gives radio mean labeling Γ of C₈ with minimum span. Consider the labels assigned to vertices v₁, v₂, v₃, v₄, v₅ which belong to path P₅. We can easily see that Γ|_V(P₅) satisfies radio mean condition and hence it is a radio mean labeling of P₅ with span = 8. However, rmn (P₅) ≤ span (Γ|_V(H)). We have already seen in Fig. 2(d) that rmn (P₅) =6. Clearly, rmn (P₅) < rmn (C₈).

Fig. 3

Radio mean labeling of C₈ with minimum span.

Now we show that rmn (G) is less than or equal to rmn (H) +2d (n - p). Here, n = 8, p = 5, d = 4. Consider a radio mean labeling γ of P₅ with span = rmn (P₅) =6 as in Fig. 2(d). Define a labeling Γ of C₈ such that Γ (v_i) = γ (v_i) , i = {1, 2, ⋯ , 5} and Γ (v_i) =6 + 8 (i - 5) , i = {6, 7, 8}. We can easily verify that Γ is a radio mean labeling of C₈ with span = 30. See Fig.4. However, rmn (C₈) =8. Clearly, rmn (C₈) < rmn (P₅) +8 × (3) =30.

Fig. 4

Radio mean labeling of C₈ with span = 30.

Theorem 2.1 holds in the case when H is a diametral path of G. Hence we have

Corollary 1.1.If G is a graph having order n and diameter d and P_d+1 is a diametral path in G, then $rmn (P_{d + 1}) \leq rmn (G) \leq rmn (P_{d + 1}) + 2 d (n - d - 1) .$

2.2 Bounds for radio mean number in terms of order and diameter

Radio mean labelings of the path graph were studied in the paper [22]. Using their results (Theorems 2, 3, and 6) we have improved the bounds on radio mean number of a graph of order n and diameter d ≥ 4. It has already been proved in [12] that graphs of diameter either 2 or 3 are radio mean graceful. Here, we give an alternative proof for the same with the help of Theorems 2 and 3.

Theorem 2. [22] For m = 2, 3, radio mean number of path P_m is m.

See Figs. 5 and 6 for radio mean labelings with minimum span of paths P₂ and P₃ respectively.

Fig. 5

P₂ with minimum span Radio mean labeling.

Fig. 6

P₃ with minimum span Radio mean labeling.

Theorem 3. [22] For m = 4, 5, 6, radio mean number of path P_m is 2m - 4.

See Figs. 7, 2(d) and 6 for radio mean labelings with minimum span of paths P₄, P₅ and P₆ respectively.

Fig. 7

P₄ with minimum span Radio mean labeling.

Fig. 8

P₆ with minimum span Radio mean labeling.

Theorem 4. If G is a graph of order n > 1 and diameter d = 1, 2 or 3, then $rmn (G) = n .$

Proof. Suppose G is a graph with vertex set {v₁, v₂, ⋯ , v_n} , n > 1 and diameter d = 1, 2 or 3. Let P_d+1 : v₁v₂ ⋯ v_d+1 be a diametral path in G. Let f be a radio mean labeling of P_d+1 with span of f = rmn (P_d+1) = d + 1. Now let us define a function F on V (G) in such a way that $F (v) = {\begin{matrix} f (v) : if v \in V (P_{d + 1}) \\ k : if v \in V (G) \ V (P_{d + 1}) \\ where k \in {d + 2, d + 3, \dots, n} \end{matrix}$ and for .

Let (u₁, u₂, ⋯ , u_n) be an arrangement of vertices of G such that F (u_i) < F (u_j) , 1 ≤ i < j ≤ n where F (u_i) = i. Here F maps distinct integers to distinct vertices. We shall now check if F satisfies radio mean condition. Consider u_a, u_b ∈ V (G) where 1 ≤ a, b ≤ d + 1, a ≠ b . $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ \frac{f (u_{a}) + f (u_{b})}{2} ⌉ \\ + d (u_{a}, u_{b}) \\ \geq & d + 1 . \end{matrix}$ Consider u_a, u_b ∈ V (G) where d + 2 ≤ a, b ≤ n, a ≠ b . size911 $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ \frac{a + b}{2} ⌉ + d (u_{a}, u_{b}) \\ \geq & d + 1, as a, b > d + 1 . \end{matrix}$ Consider u_a, u_b ∈ V (G) such that 1 ≤ a ≤ d + 1 and d + 2 ≤ b ≤ n. size9.511.5 $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ \frac{a + b}{2} ⌉ + d (u_{a}, u_{b}) \\ \geq & d + 1, as d = 1, 2 or \\ 3, a \geq 1, b \geq d + 2 . \end{matrix}$

Hence F defines a radio mean labeling of G with span (F) = n. Since rmn (G) is at least the order of G and is the minimum span of all feasible radio mean labelings of G, we have n ≤ rmn (G) ≤ span (F) = n . Therefore, rmn (G) = n .□

We know that for a connected graph G of order n, rmn (G) ≥ n. However, the theorem 2.2 states that if diameter is 1, 2 or 3, G is radio mean graceful. See figures Figs. 9, 10 and 11 for radio mean labeled graphs of order 8 whose diameter d ∈ {1, 2, 3}. In each case, the radio mean labeling shown in figure has a span 8. It is obvious that there does not exist a radio mean labeling with span less than 8 for these graphs as their order are 8. This implies that for each of these graphs of order 8, radio mean number is also 8.

Fig. 9

Graph of order 8 and diameter 1 with Radio mean labeling.

Fig. 10

Graph of order 8 and diameter 2 with Radio mean labeling.

Fig. 11

Graph of order 8 and diameter 3 with Radio mean labeling.

Theorem 5.If G is a graph of order n ≥ 5 and diameter d = 4 or 5, then $2 d - 2 \leq rmn (G) \leq n + d - 3 .$

Proof. Suppose G is a graph with vertex set {v₁, v₂, ⋯, v_n}, n ≥ 5 and diameter d = 4 or 5. Let P_d+1 : v₁v₂ ⋯ v_d+1 be a diametral path in G. Let f be a radio mean labeling of P_d+1 with rmn (P) = span of f = 2d - 2 defined by $f (v_{i}) = {\begin{matrix} d - 2 : i = 1, \\ 2 d - 2 : i = 2, \\ d - 1 : i = 3, \\ 2 d - i + 1 : 4 \leq i \leq d + 1 . \end{matrix}$ Then by corollary 1.1 rmn (P_d+1) =2d - 2 ≤ rmn (G) . Now let us define a function F on V (G) in such a way that $F (v) = {\begin{matrix} f (v) : if v \in V (P_{d + 1}) \\ k : if v \in V (G) \ V (P_{d + 1}) \\ where k \in {2 d - 1, 2 d, \dots, d + n - 3} \end{matrix}$ and for . The range of F is given by {d + i - 3 :1 ≤ i ≤ n}.

Let (u₁, u₂, ⋯ , u_n) be an ordering of vertices of G such that F (u_i) < F (u_j). It is clear from the definition of F that F maps distinct integers to distinct vertices. We shall now check if F satisfies radio mean condition. Consider u_a, u_b ∈ V (G) where 1 ≤ a, b ≤ d + 1, a ≠ b . $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ \frac{f (u_{a}) + f (u_{b})}{2} ⌉ \\ + d (u_{a}, u_{b}) \\ \geq & d + 1 \end{matrix}$ Consider u_a, u_b ∈ V (G) where d + 2 ≤ a, b ≤ n, a ≠ b . $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ d + \frac{a + b}{2} - 3 ⌉ \\ + d (u_{a}, u_{b}) \\ \geq & d + 1, as a, b > d . \end{matrix}$ Consider u_a, u_b such that 1 ≤ a ≤ d + 1 and d + 2 ≤ b ≤ n. $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ d + \frac{a + b}{2} - 3 ⌉ \\ + d (u_{a}, u_{b}) \\ > & d + 1, as a \geq 1, \\ b \geq d + 2 . \end{matrix}$ Thus, F : V (G) ⟶ {1, 2, ⋯ , 2d - 2, 2d - 1, 2d, 2d + 1, ⋯ , n + d - 3} is a one-one function that satisfies the radio mean condition and hence F defines a radio mean labeling of G. The maximum integer in the range of F is n + d - 3. Therefore, by the definition of radio mean number of G, we have rmn (G) ≤ n + d - 3.□

Now let us verify if the theorem 5 holds for a graph G with n = 5, d = 4. By this theorem, 5 ≤ rmn (G) ≤6. Consider P₅. In Fig.2, we have already discussed the different radio mean labelings of P₅ and have shown that rmn (P₅) =6. This validates the 2.2 when n = 5, d = 4. Now suppose that n = 8 and d ∈ {4, 5}. If d = 4, 6 ≤ rmn (G) ≤9 and if d = 5, 8 ≤ rmn (G) ≤10. See Fig.12 for a radio mean labeled graph of order 8 and diameter 4 and Fig. 13 for a radio mean labeled graph of order 8 and diameter 5. For either of these graphs, we can see that there do not exist radio mean labelings with span less than the ones shown in figure. Hence the radio mean number of the graph in Fig.12 is 9 and that of the graph in Fig.13 is 10. This shows that the lower and upper bound claimed in the theorem are sharp.

Fig. 12

Radio mean labeled graph of order 8 and diameter 4.

Fig. 13

Radio mean labeled graph of order 8 and diameter 5.

Theorem 6.[22] For Path P_m where m ∈ [4 + S_k, 6 + S_k + k], $S_{k} = \frac{k (k + 5)}{2}$ and k = 1, 2, 3, ⋯, the function $f : V (P_{m}) ⟶ ℤ^{+}$ given by $\begin{matrix} (i) & f (v_{1}) = & m - k - 3 \\ (ii) & f (v_{d_{i}}) = & m - k + i - 4, if i = 2, 3, \dots, k + 2 \\ (iii) & f (v_{i}) = & 2 m - i - 1, if (d_{k + 2}) + 1 \leq i \leq m \\ (iv) & f (v_{i}) = & f (v_{(d_{l} + 1)}) + d_{l} - i, if i \in (d_{l - 1}, d_{l}) \\ where l \in {k + 2, k + 1, \dots, 2} \end{matrix}$ defines a radio mean labeling of P_m with span 2m - k - 4 . Here, d₁ = 1, and d_i = d_i-1 + n - f (v_{d
_i-1}) -1 ; i = 2, 3, ⋯ , k + 2. Also, the radio mean number of P_m is 2m - k - 4.

Consider path P₇ : v₁v₂ ⋯ v₇. We radio mean label P₇ by theorem 6 as follows: Here m = 7, k = 1, S₁ = 3 so that 7 ∈ [4 + S₁, 6 + S₁ + 1].

(i) v₁ ← 3

(ii) v₄ ← 4, v₆ ← 5

(iii) v₇ ← 6

(iv) v₅ ← 7, v₃ ← 8, v₂ ← 9

Hence, rmn (P₇) =9. See Fig. 14 for radio mean labeling with minimum span of paths P₇.

Fig. 14

P₇ with minimum span Radio mean labeling.

Theorem 7.If G is a graph of order n ≥ 7 and diameter d ≥ 6, then $2 d - k - 2 \leq rmn (G) \leq n + d - k - 3$ where d + 1 ∈ [4 + S_k, 6 + S_k + k], $S_{k} = \frac{k (k + 5)}{2}$ and k = 1, 2, 3, ⋯.

Proof. Suppose G is a graph with vertex set {v₁, v₂, ⋯ , v_n}, n ≥ 7 and diameter d ≥ 6. Let P_d+1 : v₁v₂ ⋯ v_d+1 be a diametral path in G. Let f be a radio mean labeling of P_d+1 as in Theorem 6 with rmn (P_d+1) = span of f = 2d - k - 2 where d + 1 ∈ [4 + S_k, 6 + S_k + k], $S_{k} = \frac{k (k + 5)}{2}$ and k = 1, 2, 3, ⋯. Then by corollary 1.1, $rmn (P_{d + 1}) = 2 d - k - 2 \leq rmn (G) .$ Now let us define a function F on V (G) in such a way that $F (v) = {\begin{matrix} f (v) : if v \in V (P_{d + 1}) \\ i : if v \in V (G) \ V (P_{d + 1}) \\ where i \in {2 d - k - 1, 2 d - k, \dots, \\ n + d - k - 3} \end{matrix}$ and for . The range of F is given by {d + i - k - 3 :1 ≤ i ≤ n}.

Let (u₁, u₂, ⋯ , u_n) be an arrangement of vertices of G such that F (u_i) < F (u_j) , 1 ≤ i < j ≤ n. It is clear that F maps distinct integers to distinct vertices. We shall now check if F satisfies radio mean condition. Consider u_a, u_b ∈ V (G) where 1 ≤ a, b ≤ d + 1, a ≠ b . $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ \frac{f (u_{a}) + f (u_{b})}{2} ⌉ \\ + d (u_{a}, u_{b}) \\ \geq & d + 1 . \end{matrix}$ Consider u_a, u_b where d + 2 ≤ a, b ≤ n, a ≠ b . size9.511.5 $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ d + \frac{a + b}{2} - k - 3 ⌉ \\ + d (u_{a}, u_{b}) \\ \geq & d + 1, as a, b > d, \\ k ⪡ d . \end{matrix}$ Consider u_a, u_b such that 1 ≤ a ≤ d + 1 and d + 2 ≤ b ≤ n. size9.511.5 $\begin{matrix} ⌈ \frac{F (u_{a}) + F (u_{b})}{2} ⌉ + d (u_{a}, u_{b}) & = & ⌈ d + \frac{a + b}{2} - k - 3 ⌉ \\ + d (u_{a}, u_{b}) \\ > & d + 1, as a \geq 1, \\ b \geq d + 2, k ⪡ d . \end{matrix}$ Thus, F : V (G) ⟶ {1, 2, ⋯ , 2d - k - 2, 2d - k - 1, 2d - k, 2d - k + 1, ⋯ , n + d - k - 3} is a one-one function which satisfies radio mean condition and hence F defines a radio mean labeling of G. The maximum integer in the range of F is n + d - k - 3 where k is the integer such that d + 1 ∈ [4 + S_k, 6 + S_k + k], $S_{k} = \frac{k (k + 5)}{2}$ and k = 1, 2, 3, ⋯. Therefore, by the definition of radio mean number of G, we have $rmn (G) \leq n + d - k - 3$ where k is the integer such that d + 1 ∈ [4 + S_k, 6 + S_k + k], $S_{k} = \frac{k (k + 5)}{2}$ and k = 1, 2, 3. . .

Now let us verify if the theorem 7 holds for a graph G with n = 7, d = 6. Here G is isomorphic to path P₇. By theorem 2.2, rmn (P₇) =9. See Fig.14. This validates the theorem 2.2 and shows that lower bound is attained. Now we consider two graphs of order 8 with diameter 6 and 7 respectively. See Figs. 15 and 16 where the graphs are radio mean labeled. For either of these graphs, there do not exist radio mean labelings with span less than the ones shown in figure. Hence the radio mean numbers of graphs in Figs.15 and 16 are 10 and 11 respectively. This shows that the upper bound claimed in the theorem is sharp.

Fig. 15

Radio mean labeled graph of order 8 and diameter 6.

Fig. 16

Radio mean labeled graph of order 8 and diameter 7.

Summarizing the above results, we have that if G is a graph on n vertices with diameter d, then

rmn (G) = n : if d = 1, 2, 3,

2d - 2 ≤ rmn (G) ≤ n + d - 3 : if d = 4, 5,

2d - k - 2 ≤ rmn (G) ≤ n + d - k - 3 : if d = 6, 7, 8, 9, ⋯ , $d + 1 \in [4 + S_{k}, 6 + S_{k} + k], S_{k} = \frac{k (k + 5)}{2} and k = 1, 2, 3, \dots$ .

The limit on the Right-hand side of the above inequalities 1 and 2 is maximum when the diameter d is maximum. Graphs isomorphic to path P_n on n vertices are the graphs having maximum diameter among the set of all graphs of order n. For P_n, d = n - 1. We will consider the following cases: Case: 1 When n = 2, the maximum diameter possible is 1 and for P₂, by theorem 2, rmn (P₂) =2. When n = 3, the maximum diameter possible is 2 and for P₃, by theorem 2, rmn (P₃) =3. When n = 4, the maximum diameter possible is 3 and for P₄, by theorem 3, rmn (P₄) =4. Case: 2 If n = 5, the maximum possible diameter is d = n - 1 =4 and then the limit on the Right-hand side of the inequality in theorem 5 is n + d - 3 =6 and if n = 6, the maximum possible diameter d is 5 and then the limit on the Right-hand side of the inequality in theorem 5 is n + d - 3 =8. Among all graphs of order 5, P₅ has the maximum diameter and by theorem 3, rmn (P₅) =2 × 5 -4 = 6. Among all graphs of order 6, P₆ has the maximum diameter and by theorem 3, and rmn (P₆) =2 × 6 -4 = 8. Case: 3 Let n ≥ 7. If d ≥ 6,

d + 1 \in [4 + S_{k}, 6 + S_{k} + k], S_{k} = \frac{k (k + 5)}{2} and k \in ℤ^{+}

, the maximum possible diameter of a graph of order n is d = n - 1. Then the limit on the Right-hand side of the inequality in theorem 7 is n + d - k - 3 = n + (n - 1) - k - 3 =2n - k - 4. By theorem 6, for path P_n, where n ≥ 6,

n \in [4 + S_{k}, 6 + S_{k} + k], S_{k} = \frac{k (k + 5)}{2} and k \in ℤ^{+}

, rmn (P_n) =2n - k - 4.

Thus, the maximum radio mean number possessed by any graph of order n is equal to rmn (P_n). The minimum radio mean number possessed by any graph of order n is n. In other words, we have the following theorem.

Theorem 8. If G is a connected graph on n vertices, n ≤ rmn (G) ≤ rmn (P_n) .

Illustration: Path P₂₀ possesses the maximum radio mean number among the class of all graphs of order 20

Consider all graphs of order 20. Then 20 ∈ [4 + S_k, 6 + S_k + k] where S_k = 12, k = 3. By Theorem 7, an upper bound of radio mean number of graphs of order 20 is 20 + d - 3 -3 = 14 + d which is maximum when d is maximum. The maximum possible value of diameter, d is 19 when the order is 20. Hence, the upper bound of the radio mean number of graphs of order 20 is 33.

Let P₂₀ : v₁v₂ ⋯ v₂₀ be a path of order 20. A radio mean labeling of P₂₀ by Theorem 6 is as follows: v₁ ⟼ 14, v₂ ⟼ 33, v₃ ⟼ 32, v₄ ⟼ 31, v₅ ⟼ 30, v₆ ⟼ 15, v₇ ⟼ 29, v₈ ⟼ 28, v₉ ⟼ 27, v₁₀ ⟼ 16, v₁₁ ⟼ 26, v₁₂ ⟼ 25, v₁₃ ⟼ 17, v₁₄ ⟼ 24, v₁₅ ⟼ 18, v₁₆ ⟼ 19, v₁₇ ⟼ 20, v₁₈ ⟼ 21, v₁₉ ⟼ 22, v₂₀ ⟼ 23. So the radio mean number of P₂₀ is 33, the maximum achievable radio mean number by a graph of order 20.

2.3 Improved upper bound of radio mean number

Ponraj et. al in [12] showed that that for any graph G on n vertices with diameter d, $rmn (G) \leq n + d - 2$ (1)

If d = 4, then by 1, rmn (G) ≤ n + 2 and by Theorem 5, rmn (G) ≤ n + 1. If d = 5, then by 1, rmn (G) ≤ n + 3 and by Theorem 5, rmn (G) ≤ n + 2. For any n, if d = 4 or 5, Theorem 5 gives an improved bound on the radio mean number of a graph than the bound obtained in [12].

For any given n, if d ≥ 6, we have n + d - 2 > n + d - k - 3. Note that k is a positive integer whose value depends on the value of d. For any n, if d ≥ 6, Theorem 7 gives an improved bound on the radio mean number of a graph than the bound obtained in [12].

Consider the class of all graphs of order n. Then the diameter, d of these graphs lies between 1 and n - 1. Table 1 compares the upper bound on these graphs’ radio mean number, as derived in section 2.2, with the bound obtained in [12]. We conclude that the upper bound of the radio mean number of any graph, as given in section 2.2, is much less than the bound mentioned in [12].

Table 1

A comparison of bounds on radio mean number of graphs of order n and diameter d, 1 ≤ d ≤ n - 1, as derived in [12] with the bounds obtained in Section 2.2

d	k	Upper bound	Upper bound
		as in [12]	as in sec. 2.2
1	0	n-1	n-2
2	0	n	n-1
3	0	n+1	n
4	0	n+2	n+1
5	0	n+3	n+2
6	1	n+4	n+2
7	1	n+5	n+3
8	1	n+6	n+4
9	1	n+7	n+5
10	2	n+8	n+5
11	2	n+9	n+6
12	2	n+10	n+7
13	2	n+11	n+8
14	2	n+12	n+9
15	3	n+13	n+9
16	3	n+14	n+10
17	3	n+15	n+11
18	3	n+16	n+12
19	3	n+17	n+13
20	3	n+18	n+14
⋮	⋮	⋮	⋮
n-1	k	2n-3	2n-k-4

Illustration: Improved upper bound of radio mean number of cycle C₂₀

Consider the cycle C₂₀ with 20 vertices namely, v₁, v₂, ⋯ , v₁₉, v₂₀. For C₂₀, diameter, $d = ⌊ \frac{20}{2} ⌋ = 10$ . By 1, radio mean number of C₂₀, $rmn (C_{20}) \leq n + d - 2 = 20 + 10 - 2 = 28 .$ (2) Let P₁₁ : v₁v₂v₃v₄v₅v₆v₇v₈v₉v₁₀v₁₁ be a path of length d = 10. Then 11 ∈ [4 + S_k, 6 + S_k + k] where S_k = 3 +4, k = 2 . Hence as discussed in the proof of above theorem, we label the vertices belonging to P₁₁ as follows: v₁ ⟼ 6, v₂ ⟼ 16, v₃ ⟼ 15, v₄ ⟼ 14, v₅ ⟼ 7, v₆ ⟼ 13, v₇ ⟼ 12, v₈ ⟼ 8, v₉ ⟼ 11, v₁₀ ⟼ 9, v₁₁ ⟼ 10. The remaining unlabelled vertices of C₂₀ are now assigned labels as follows: v_i ⟼ i + 5, i = 12, 13, ⋯ , 20 . This assignment is a radio mean labeling of C₂₀ with span 25. Therefore, radio mean number of C₂₀, $rmn (C_{20}) \leq 25 .$ (3) From 2 and 3, it is clear that the bound proposed in [12] is improved in Theorem 7.

3 Applications of radio mean labeling

See [7] for a detailed listing of all graph labelings and their applications. Let us now see two scenarios in cryptography where radio mean labeling of graphs can be used.

3.1 Radio mean labeled graph as cipher graph

In [23], authors have combined techniques of cryptography together with graph labeling for secure communication of messages. The plaintext encrypted by Playfair cipher substitution and transposition technique is sent to the receiver as a sequence of edges or vertices of a cipher graph representing encrypted text. The receiver can decrypt the received sequence of numbers to the original text message using the radio mean labeled cipher graph. The steps involved in encryption and decryption processes are briefly listed below. Encryption process:

Divide the plain text into pairs of letters.

Construct a 6 × 6 Playfair matrix and apply Playfair cipher techniques to the given plain text.

Interchange positions of characters in cipher text based on a predefined rule.

Represent the characters in cipher text after transposition as numbers according to a predefined numbering system.

A sequence of edges/vertices of cipher graph representing the output of step 4 is sent to the receiver.

Decryption process: The receiver can decrypt the text to retrieve the original message as follows:

Obtain the number sequence corresponding to the received sequence of vertices and edges.

Represent the numbers in the sequence obtained in step 1 as characters.

Transpose the characters in the output of step 2.

Apply substitution rules using the Playfair matrix and obtain the original message.

3.2 Radio mean labeled graphs for key generation

Generally, the keys for cryptographic algorithms are generated by strong random number generators. The article [24] proposes the idea of developing keys for cryptographic algorithms using the techniques of radio mean labeling. The algorithm in the scope of this article is Triple DES with keys, K1 and K2. An algorithm to obtain a radio mean labeling of a particular type of caterpillar tree, C, is provided in the article. Keys are generated as follows:

Pick two integers as the order, n > 0 and diameter, d ≤ n - 1 of the caterpillar tree C.

Let c₁c₂ ⋯ c_d+1 be a path on d + 1 vertices. The vertex c₂ is made adjacent to n - (d + 1) vertices, namely, c_d+2, c_d+3, ⋯ , c_n. The resultant graph is C.

Radio mean label C using the proposed algorithm.

Key K1 is the labels of vertices belonging to the central path of C.

Key K2 is the labels of vertices not belonging to the central path of C.

Let

E_{Kitsc}

and

D_{Kitsc}

represent DES encryption with key K and DES decryption with key K, respectively. Encryption process:

Sender generates two keys.

If $M$ is the original message, then the Triple DES algorithm encrypt it as $C = E_{K 1} (D_{K 2} (E_{K 1} (M)))$ .

Sender may send the cipher text, $C$ along with the order and diameter of the cipher graph, each delimited by a semicolon, to the receiver in the format: $< n; d; C >$ .

Decryption process:

Upon receiving the cipher text, $C$ , the receiver constructs a caterpillar graph, and radio mean label it and extracts keys K1 and K2 from the cipher graph.

The original message, $M = D_{K 1} (E_{K 2} (D_{K 1}$ $(C)))$ .

4 Conclusion

Finding any radio mean labeling of a given graph is a non-trivial task and so is labeling it with minimum radio mean number. In this paper, the authors have derived upper and lower bounds for the radio mean number of a given graph in terms of its order and diameter. For any connected graph G of order n and diameter d, we proved that

rmn (G) = n : if d = 1, 2, 3,

2d - 2 ≤ rmn (G) ≤ n + d - 3 : if d = 4, 5,

2d - k - 2 ≤ rmn (G) ≤ n + d - k - 3 : if d = 6, 7, 8, 9, ⋯ , $d + 1 \in [4 + S_{k}, 6 + S_{k} + k], S_{k} = \frac{k (k + 5)}{2} and k = 1, 2, 3, \dots$ .

It is also observed that the minimum and maximum radio mean number achieved by any graph of order n are n and rmn (P_n), respectively. All graphs of diameters 1,2 and 3 are radio mean graceful. However, these are not the only graphs on n vertices with radio mean number n. Characterization of such graphs is an open problem. For any n, whether every integer between n and rmn (P_n) is the radio mean number of some graph of order n is another open problem. Articles [23, 24] discuss applications of radio mean labeling technique, and more research is expected in the future.

Footnotes

Acknowledgment

The authors wish to extend their special thanks to Prof. Gyula O. H. Katona for his valuable remarks on this article when he visited Amrita Vishwa Vidyapeetham, India, in July 2022. In addition, the authors thank all anonymous referees for their suggestions and comments.

References

Ahmad

, Ali

, Zafar

and Zahid

, Some new standard graphslabeled by 3-total edge product cordial labeling, AppliedMathematics and Nonlinear Sciences 2(1) (2017), 61–72.

Ali

, Zafar

and Zahid

, Some families of convex polytopes labeled by 3-total edge product cordiallabeling, Punjab University Journal of Mathematics 49(3) (2020).

Ali

, Iqbal

, Zafar

and Zahid

, 4-total edge productcordial labeling of some standard graphs, Tamap Journal of Mathematics and Statistics 16 (2018), 31.

Aslam

, Zahid

and Zafar

, 3-total edge mean cordial labelingof some standard graphs, Open Journal of Mathematical Sciences 3(1) (2019), 129–138.

Chartrand

, Erwin

, Harary

and Zhang

, Radio labelings ofgraphs, Bull. Inst. Combin. Appl 33 (2001), 77–85.

Das

, Samanta

and Pal

, Study on centrality measures insocial networks: a survey, Social Network Analysis and Mining 8(1) (2018), 1–11.

Gallian

J.A.

, A dynamic survey of graph labeling, Electronic Journal of Combinatorics 1(DynamicSurveys) (2018), DS6.

Gross

J.L.

, Yellen

, Anderson

Graph theory and its applications, Chapman and Hall/CRC (2018).

Lavanya

and Meera

K.N.

, Radio mean graceful graphs, In Journal of Physics: Conference Series 1172(1) (2019) 012071). IOP Publishing.

10.

Liu

D.D.F.

and Zhu

, Multilevel distance labelings for paths andcycles, SIAM Journal on Discrete Mathematics 19(3) (2005), 610–621.

11.

Meera

K.N.

, Radio geometric graceful graphs, In67). IOP Publishing, IOP Conference Series: Materials Science and Engineering 577(1) (2019), 012167). IOP Publishing.

12.

Ponraj

, Narayanan

S.S.

and Kala

, Radio mean labeling of agraph, AKCE International Journal of Graphs and Combinatorics 12(2–3) (2015), 224–228.

13.

Ponraj

, Narayanan

S.S.

and Kala

, On radio mean number of somegraphs, International J. Math. Combin 3 (2014), 41–48.

14.

Ponraj

, Narayanan

S.S.

and Kala

, Radio mean number of somewheel related graphs, Jordan Journal of Mathematics andStatistics (JJMS) 7(4) (2014), 273–286.

15.

Ponraj

, Narayanan

S.S.

and Kala

, Radio mean number of somesubdivision graphs, Jordan Journal of Mathematics andStatistics (JJMS) 9(1) (2016), 45–64.

16.

Ponraj

and Narayanan

S.S.

, Radio mean number of certain graphs, International Journal of Mathematical Combinatorics 2(2016), 51.

17.

Poulik

and Ghorai

, Determination of journeys order based ongraph’s Wiener absolute index with bipolar fuzzy information, Information Sciences 545 (2021), 608–619.

18.

Poulik

, Ghorai

Applications of graph’s complete degreewith bipolar fuzzy information, Complex & Intelligent Systems (2021), 1–13.

19.

Poulik

and Ghorai

, Empirical results on operations of bipolarfuzzy graphs with their degree, Missouri Journal of Mathematical Sciences 32(2) (2020), 211–226.

20.

Poulik

, Ghorai

New concepts of inverse fuzzy mixed graphsand its application, Granular Computing (2021), 1–11.

21.

Poulik

, Ghorai

Estimation of most effected cycles andbusiest network route based on complexity function of graph in fuzzyenvironment, Artificial Intelligence Review (2022), 1–18.

22.

Saraswathi

and Meera

K.N.

, Radio mean labeling of paths and itstotal graph, Turkish Journal of Computer and MathematicsEducation (TURCOMAT) 12(1S) (2021), 343–350.

23.

Saraswathi

, Meera

K.N.

An application of radio mean labelingin cryptography, In 2021 IEEE 3rd PhD Colloquium on Ethically Driven Innovation and Technology for Society (PhD EDITS) IEEE (2021), 1–2.

24.

Saraswathi

and Meera

K.N.

, Radio mean labeled graphs to generatekeys in cryptography, In 2021 2nd International Conference onCommunication, Computing and Industry, IEEE 4.0(C2I4) (2021), 1–3.

25.

Saraswathi

, Meera

K.N.

Comments on an integer linear programming model for solving radio mean labeling problem, IEEEAccess (2022).

26.

Sunitha

, Raj

C.D.

and Subramanian

, Radio mean labeling of pathand cycle related graphs, Global Journal of MathematicalSciences: Theory and Practical 9(3) (2017), 337–345.

27.

West

D.B.

, Upper Saddle River: Prentice Hall, Introduction to Graph Theory 2 (2001).