Radio number of $2-$ super subdivision for path related graphs

1.   Introduction

In recent years, several fascinating research areas have emerged within the field of study associated with graph theory. Concerning these, graph labeling constitutes a highly intriguing and dynamic field that encompasses numerous applications. There are a number of different scientific fields that utilize graph labeling, such as communication networks, database administration, coding theory, and many others. The concept was initially proposed by ^[1]. Recently, numerous types of labeling have been extensively studied, such as graceful labeling by ^[2], (modular) irregular labeling by ^[3], edge labeling by ^[4] and so on. All graphs, denoted as $G = (V, E)$, in the presented work are simple un$-$directed, connected, and finite. Here, $V$ represents the vertex set, and $E$ represents the edge set of $G$. The graph labeling assignment involves assigning integers regarding vertices $(v)$, edges $(e)$, or both, according to specific conditions. Radio labeling is a technique that is used to address the challenge of channel assignment. With graph $G$, there exist several different radio labeling challenges. One of the foremost significant contributions to this field was conducted by ^[5], whose primary findings consisted of determining the precise values of $rn(G)$ for paths and cycles. This is one of the most well$-$known studies in this area.

The channel assignment problem, initially proposed by ^[6] and later revisited by ^[7], is mainly motivated by the need to comply with regulations on the allocation of channels for FM broadcasting stations. This problem aimed to incorporate the concept of radio labeling of graphs also referred to as multilevel distance labeling. The radio labeling problem is an important topic in discrete mathematics due to its various applications, like in frequency assignment in mobile communication systems, signal processing, circuit design, etc. ^[8] found the upper boundaries to obtain the radio numbers associated with the cycle. ^[5] determined an accurate value for the radio number of paths. ^[9] stated that three sufficient and necessary conditions must be met to attain the lower bound for the radio number of the block graph. Radio numbers of line graphs of trees and block graphs have also been discussed by the same authors. According to ^[10], the problem of radio channel assignment for the network is modeled by Cayley graphs. A discussion of the radio number of the Cartesian product of two trees can be found in ^[11]. The study of ^[12] have introduced supersubdivision of graphs.

To better illustrate the channel assignment problem scopes of radio labeling and the major contributions of theoretical as well as practical significance of this article, we provide Table 1 for comparison with other research works on the radio number of different graphs.

2.   Notation

This section starts with an overview of the notations that will be applied throughout the paper, listed in Table 2.

3.   Preliminaries

This study consists of defining essential terms and notations in this section that will be used throughout the entire research paper. One may refer to ^[25] for all terminologies and notations and ^[26] for graph labeling. A graph $G$'s shortest path is measured by the distance $d(u, v)$ between two vertices. $diam(G) = max\{d(u, v) : u, v \in G\}$ is the diameter of a graph $G$ (or simply $d$ for use in equations). Although eccentricity can be defined in many ways, it is usually referred to as the distance between a certain vertex ($v$) and any other vertex in a graph ($G$) at which the vertex is at its maximum value. The eccentricity is denoted by $\varepsilon(v)$ through this concept. A sub$-$graph is defined here as the vertex whose eccentricity is lowest and which is the center of the graph $G$, called $C(G)$.

Definition 3.1. (^[7]) In a graph $G,$ the radio labeling is a mapping $\varpi:V(G) \rightarrow \{0, 1, 2, 3, ..., \},$ such as $|\varpi(\mu')-\varpi(\mu'')|\geq diam(G)+1-d(\mu', \mu'').$ A label of $\mu$ under $\varpi$ is defined by the integer $\varpi(\mu),$ and the span under is defined by $span(\varpi) = max \{|\varpi(\mu')-\varpi(\mu'')|: \mu', \mu'' \in V(G)\}.$ $rn(G) = min_{\varpi} span(\varpi)$ is defined as the radio number of $G$ when the minimum over all radio labeling $\varpi$ of $G$ is taken. $G$ is said to be optimal if it's radio labeling is $span(\varpi) = rn(G).$

Definition 3.2. (^[27]) The $2-$super subdivision graph $SS(G, m)$ is constructed from the original graph $G$ by changing each of the edges with a complete bipartite graph $K_{m, m}$ where $m = 2$. This substitution involves combining each endpoint of the edge with any two vertices from either partite set $X$ or $Y$ of $K_{m, m}$ when removing the original edge from $G$.

Illustration: The following Figures 1 and 2 are the examples for definition (3.2).

Lemma 3.1. $C(SS(P_n; 2)) = \begin{cases} 2 K_{1} & \mathit{\text{if n is even}}\\ K_{1} & \mathit{\text{otherwise}}. \end{cases}$

Proof. Let $SS(P_n; 2)$ a $2$ super subdivision of a path $P_n$ and $S$ be a collection of all vertices in $SS(P_n; 2)$ which have the lowest possible eccentricity. The eccentricity for vertex $v ^{'}_{i}$ $(v^{''}_{j})$ if $1 \leq i \leq n$ $(1 \leq j \leq 2n-2)$ can be expressed as follows:

Case 1: If $n$ is an odd number.

$\varepsilon(v^{'}_{i}) = (n-1)+|2i-(n+1)|$, if $1 \le i \le n$.

$\varepsilon(v_{j}^{''}) = \begin{cases} 2n-j-2, & \text{if} \ j = 1, 3, ..., n-2, \\ 2n-j-1, & \text{if}\ j = 2, 4, ..., n-1, \\ j, & \text{if}\ j = n, n+2, ..., 2n-3, \\ j-1, & \text{if}\ j = n+1, n+3, ..., 2(n-1). \end{cases}$

One can see that $S$ contains only $v^{'}_{\frac{n+1}{2}}$. Thus, by the above function, $\varepsilon(v^{'}_{\frac{n+1}{2}})$ is smaller than the eccentricity of the remaining vertices in $SS(P_n; 2)$. The graph indued by $S$ is isomorphic to the complete graph $K_1$ and hence $C(SS(P_n; 2)) = K_1.$

Case 2: If $n$ is an even number.

$\varepsilon(v^{'}_{i}) = \begin{cases} 2(n-i), & \text{if}\ 1 \le i \le \frac{n}{2}, \\ 2(i-1), & \text{if}\ \frac{n+2}{2} \le i \le n. \end{cases}$

$\varepsilon(v^{''}_{j}) = \begin{cases} |n-j-1|+(n-1), & \text{if}\ j = 1, 3, ..., 2n-3, \\ |n-j|+(n-1), & \text{if}\ j = 2, 4, ..., 2n-2. \end{cases}$

One can see that $S = \{v^{''}_{n-1}, v^{''}_{n} \}$. Since the graph induced by $S$ has the same isomorphic relations as the complete graph $2K_1$, we can conclude that case (2) is $C(SS(P_n; 2)) = 2 K_{1}$.

Let us now consider the new denotation of the vertex of $SS(P_n; 2)$ with respect to its center. $SS(P_n; 2)$'s vertices are renamed accordingly.

If $n$ is an odd number, then let $n = 2k+1$

$v^{'}_{i} = \begin{cases} v_{C = i}^{1} & \text{if}\ i = \frac{n+1}{2}, \\ v^{1}_{L(n-2i+1)} & \text{if}\ 1 \leq i \leq \frac{n-1}{2}, \\ v^{1}_{R(2i-(n+1))} & \text{if}\ \frac{n+3}{2} \leq i \leq {n-1}. \end{cases}$

$v^{''}_{j} = \begin{cases} v^{1}_{L(n-j-1)} & \text{if}\ j = 1, 3, ..., n-2, \\ v^{2}_{L(n-j)} & \text{if}\ j = 2, 4, ..., n-1, \\ v^{1}_{R(j-n+1)} & \text{if}\ j = n, n+2, ..., 2n-3, \\ v^{2}_{R(j-n)} & \text{if}\ j = n+1, n+3, ..., 2(n-1). \end{cases}$

If $n$ is an even number, then let $n = 2k$

$v^{'}_{i} = \begin{cases} v^{1}_{L(n-2i+1)} & \text{if}\ 1 \leq i \leq \frac{n}{2}, \\ v^{1}_{R(2i-(n+1))} & \text{if}\ \frac{n}{2}+1 \leq i \leq n. \end{cases}$

$v^{''}_{j} = \begin{cases} v^{1}_{C = j} & \text{if}\ j = n-1, \\ v^{2}_{C = j} & \text{if}\ j = n, \\ v^{1}_{L(n-j-1)} & \text{if}\ j = 1, 3, ..., n-3, \\ v^{2}_{L(n-j)} & \text{if}\ j = 2, 4, ..., n-2, \\ v^{1}_{R(j-n+1)} & \text{if}\ j = n+1, n+3, ..., 2n-3, \\ v^{2}_{R(j-n)} & \text{if}\ j = n+2, n+4, ..., 2(n-1). \end{cases}$

Illustration: In Figures 3 and 4, the $2$ super subdivision $SS(P_9;2)$ and $SS(P_{10};2)$.

One defines the level function towards $V(SS(P_n; 2))$ as the set of whole numbers $\mathbb{W}$ by $\ell (\mu) = min\{d(\mu, \mu^{\prime}); \mu^{\prime}\in V(C(SS(P_n; 2)))\}$ for each $\mu \in V(SS(P_n; 2))-V(C(SS(P_n; 2)))$. In the graph $SS(P_n; 2)$, the maximum level is $k = n-1$. In the graph $G$, $\ell(G)$ represents the total level, and is defined as: $\ell(G) = \sum_{\mu \in V(G)}\ell(\mu)$.

4.   Main result

In this section, the $2$ super subdivision of the path $SS(P_n; 2)$ is determined, and also the radio number of the $2$ super subdivision of the path $SS(P_n; 2)$ graph is found.

Observation:

1. $|V(SS(P_n; 2))| = \delta = 3n-2$.

2. $d(\mu, \mu^{'}) \leq \ell(\mu)+ \ell(\mu^{'}).$

3. If $\mu_i, \mu_{i+1} \in V(SS(P_n; 2))$, $0 \leq i \leq \delta-2$ are on opposite side and $d(\mu_i, \mu_{i+1}) = d(\mu_{i+1}, \mu_{i+2})$ or $d(\mu_i, \mu_{i+1}) = d(\mu_{i+1}, \mu_{i+2}) \ \pm 1$ or $d(\mu_i, \mu_{i+1}) = d(\mu_{i+1}, \mu_{i+2}) \ \pm2$.

Lemma 4.1. Let $P_n$ be a path of length $n$. The total level function of $SS(P_n; 2)$ is $\ell(SS(P_n; 2)) = \begin{cases} \frac{\left(3n^2-4n+1\right)}{2} & \mathit{\text{if}} \;n\; \mathit{\text{is an odd.}}\\ \frac{n\left(3n-4\right)}{2} & \mathit{\text{if}} \;n\; \mathit{\text{is an even.}}\\ \end{cases}$

Proof. Let $P_n$ be the path of length $n$. If $n$ is an odd number, by Lemma (3.1) $C(SS(P_n; 2))$ is a single vertex.

Consider the $n-$length path, that is $P_{n}$. If $n$ is an even number, by Lemma (3.1) $C(SS(P_n; 2))$ has $2K_1$ vertices.

Lemma 4.2. Let $\varpi$ be an assignment of distinct non-negative integers to $V(SS(P_n; 2))$, and $\mu_1, \mu_2, \mu_3, ..., \mu_\delta$ be the ordering of $V(SS(P_n; 2))$ such that $\varpi(\mu_i) < \varpi(\mu_{i+1})$ defined by $\varpi(\mu_1) = 0$ and $\varpi(\mu_{i+1}) = \varpi(\mu_i)+d+1-d(\mu_i, \mu_{i+1}).$ Then, $\varpi$ is a radio labeling if for any $1\leq i \leq \delta-1,$ the following holds:

1. $d(\mu_i, \mu_{i+1}) \leq n+1$ if $n$ is odd.

2. $d(\mu_i, \mu_{i+1}) \leq n+1$ and $d(\mu_i, \mu_{i+1}) \neq d(\mu_{i+1}, \mu_{i+2})$ if $n$ is even.

Proof. Let $\varpi(\mu_1) = 0$ and $\varpi(\mu_{i+1})\geq \varpi(\mu_i)+d+1-d(\mu_i, \mu_{i+1})$ for any $1 \leq i \leq \delta-1$ and $k = n-1$. For each $1 \leq i \leq \delta-1$, let $\varpi_i = \varpi(\mu_{i+1})-\varpi(\mu_i).$ We must prove that $\varpi$ is a radio labeling if both of the above relations hold. I.e. we have to show for any $i \neq j$, $|\varpi(\mu_i)-\varpi(\mu_j)| \geq d+1-d(\mu_i, \mu_j)$.

Case 1: When $n$ is odd, we have $d = 2k$, $k = n-1$, we let $(1)$, and we take $i > j$. then,

Case 2: When $n$ is even, we have $d = 2k$, $n-1 = k$, we let (2), and we take $i > j$. then,

If $i-j$ is even, then

If $i-j$ is odd, then

Since $i-j\neq 0$, in both cases $\varpi$ is a radio labeling and hence the result.

Theorem 4.1 (^[15]). The $rn(SS(P_2;2)) = 4$.

Proof. The radio number of $SS(P_2;2)$ is shown in Figure 5.

Theorem 4.2. If $SS(P_n; 2)$ is the $2$ super subdivision of $P_{n}$($n \geq 3$), then $rn(SS(P_n; 2)) \leq 3n^2-5n+3$.

Proof. To demonstrate the conclusion, we take two cases into consideration.

Case (1): $n$ is an even number.

For $SS(P_n; 2)$, let,

$\varpi:V(SS(P_n; 2)) \rightarrow \{0, 1, 2, ..., (3n^2-5n+3)\}$ be defined by

$\varpi(\mu_{i+1}) = \varpi(\mu_i)+d+1-\left(\ell(\mu_i)+\ell(\mu_{i+1})\right)$ for $i = 1, 2, ..., \delta-2$ and

$\varpi(\mu_{\delta}) = \varpi(\mu_{\delta-1})+d-\left(\ell(\mu_{\delta-1})+\ell(\mu_{\delta})\right)$.

We first set $\mu_{1} = v^{''}_{n-1}$, $\mu_{\delta} = v^{''}_{n}$. By observation, $\delta = 3n-2$ for $2 \le i \le \delta-1$, and we set $\mu_{h}: = v^{'}_{i}$, where

$h = \begin{cases} 3(n-2i+1), & \text{if}\ 1 \le i \le \frac{n}{2}, \\ 6(n-i)+2, & \text{if}\ \frac{n}{2}+1 \le i \le n.\\ \end{cases}$

and $\mu_{h}: = v^{''}_{j}$, where

$h = \begin{cases} 3(n-j)-2, & \text{if} \ j = 1, 3, ..., n-3, \\ 3(n-j)-1, & \text{if} \ j = 2, 4, ..., n-2, \\ 3(2n-j-1), & \text{if} \ j = n+1, n+3, ..., 2n-3, \\ 3(2n-j)-2, & \text{if} \ j = n+2, n+4, ..., 2n-2.\\ \end{cases}$

Case (2): $n$ is an odd number.

For $SS(P_n; 2)$, let

$\varpi:V(SS(P_n; 2) \rightarrow \{0, 1, 2, ..., (3n^2-5n+3)\}$ be defined by

$\varpi(\mu_{i+1}) = \varpi(\mu_i)+d+1-\left(\ell(\mu_i)+\ell(\mu_{i+1})\right)$ for $i = 1, 2, ..., \delta-2$ and

$\varpi(\mu_{\delta}) = \varpi(\mu_{\delta-1})+d-\left(\ell(\mu_{\delta-1})+\ell(\mu_{\delta})\right)$.

We first set $\mu_{1} = v^{'}_{\frac{n+1}{2}}$, $\mu_{\delta} = v^{''}_{n-2}$. By observation, $\delta = 3n-2$ for $2 \le i \le \delta-1$, and we set $\mu_{h}: = v^{'}_{i}$, where

$h = \begin{cases} 2(n-2i)+3, & \text{if}\ 1 \le i \le \frac{n-1}{2}, \\ 2(2(n-i)+1), & \text{if}\ \frac{n+3}{2} \le i \le n. \end{cases}$

and $\mu_{h}: = v^{''}_{j}$, where

$h = \begin{cases} 2n+j, & \text{if}\ j = 1, 3, ..., n-4, \\ 2n+1-2j, & \text{if}\ j = 2, 4, ..., n-1, \\ 3n-j, & \text{if}\ j = n, n+2, ..., 2n-3, \\ 4n-2j, & \text{if}\ j = n+1, n+3, ..., 2(n-1). \end{cases}$

Therefore, the vertices of $SS(P_n; 2)$ can be assigned a label equivalent to the lower bound if the requirement of Lemma (4.2) is satisfied. This is true for case (1) and case (2). Hence, $\varpi$ is a radio labeling. Thus, we have

Theorem 4.3. If $SS(P_n; 2)$ is the $2$ super subdivision of $P_{n}$($n \geq 3$), then $rn(SS(P_n; 2)) \geq 3n^2-5n+3$.

Proof. Let $SS(P_n; 2)$ be the $2$ super subdivision of the given path with order $x$ and size $y$. If $(V^{'}_{i}, V^{''}_{j})$ is the bipartition of the vertex set of $K_{2, 2}$, then $X = \sum_{i = 1}^{n}|V^{'}_{i}| = n$ and $Y = \sum_{j = 1}^{n}|V^{''}_{j}| = 2(n-1)$. Thus, $SS(P_n; 2)$ has $3n-2$ vertices and $4(n-1)$ edges. Also, the names of vertices of $V^{'}_{i}$ and $V^{''}_{j}$ are $v^{'}_{1}, v^{'}_{2}, v^{'}_{3}, ..., v^{'}_{X}$ and $v^{''}_{1}, v^{''}_{2}, v^{''}_{3}, ..., v^{''}_{Y}$ such that $X+Y = x$.

For $SS(P_n; 2)$, let,

$\varpi:V(SS(P_n; 2)) \rightarrow \{0, 1, 2, ..., (3n^2-5n+3)\}$ be defined by

$\varpi(\mu_{i+1}) = \varpi(\mu_i)+d+1-\left(\ell(\mu_i)+\ell(\mu_{i+1})\right)$ for $i = 1, 2, ..., \delta-2$ and

$\varpi(\mu_{\delta}) = \varpi(\mu_{\delta-1})+d-\left(\ell(\mu_{\delta-1})+\ell(\mu_{\delta})\right)$.

Let $\mu_1 = v^{'}_{\frac{n+1}{2}}$ and $\mu_{\delta} = v^{''}_{n-2}$ if $n$ is odd. Let $\mu_1 = v^{''}_{n-1}$ and $\mu_{\delta} = v^{''}_{n}$ if $n$ is even.

Let $\varpi$ be a radio labeling for $SS(P_n; 2)$ with a linear order $\mu_1, \mu_2, \mu_3, ..., \mu_\delta$ of vertices of $SS(P_n; 2)$ such that $\varpi(\mu_1) = 0 < \varpi(\mu_2) < \varpi(\mu_3) < \varpi(\mu_4) < ... < \varpi(\mu_{\delta})$. Then, $\varpi(\mu_{i+1})-\varpi(\mu_i)\geq d+1-d(\mu_i, \mu_{i+1})$, $\forall$ $1 \leq i \leq \delta-1$. Incorporating these $\delta-1$ on the inequalities, we obtain

Case 1: $n$ is an even number.

For $SS(P_n; 2)$, $i = 1, 2, ..., \delta-1$, by observation, we acquire

Since $\mu_1$ and $\mu_{\delta}$ are both center vertices, $\ell(\mu_1) = \ell(\mu_{\delta}) = 0$ and

By substituting (4.2) in (4.1), we get

For $SS(P_n; 2)$, $\delta = 3n-2$, $d = 2n-2$ and $\ell (SS(P_n; 2)) = \left(\frac{n\left(3n-4\right)}{2}\right)$. Substituting these into the above equation, we get

Case 2: $n$ is an odd number.

For $SS(P_n; 2)$, $i = 1, 2, ..., \delta-1$, by observation, we acquire

Since $\ell(\mu_1) = 0$, $\ell(\mu_{\delta}) = 1$ and

By substituting (4.3) in (4.1), we get

For $SS(P_n; 2)$, $\delta = 3n-2$, $d = 2n-2$ and $\ell (SS(P_n; 2)) = \left(\frac{3n^2-4n+1}{2}\right)$.

Substituting these into the above equation, we get

Thus, from above two cases we have the desired result.

Theorem 4.4. If $SS(P_n; 2)$ is the $2$ super subdivision of $P_{n}$($n \geq 3$), then $rn(SS(P_n; 2)) = 3n^2-5n+3$.

Proof. The proof is based on Theorems (4.2) and (4.3), respectively.

Example 4.1. Figure 6 demonstrates both the arrangement (ordering) of the vertices as well as the optimal radio labeling of $SS(P_9;2)$.

Example 4.2. Figure 7 demonstrates both the arrangement (ordering) of the vertices as well as the optimal radio labeling of $SS(P_{10};2)$.

5.   Conclusions

It is challenging to design a wireless network that avoids interference. Our work on this problem is based on $2$ Super divisions for paths. The goal of this work is to provide proof of radio labels for $2$ super subdivisions of paths and to obtain the exact radio numbers for the $2$ super subdivisions of path graphs. In addition, our research focuses on the application of radio labels to $2$ super subdivision of path graphs.

Conflict of interests

All authors declare no conflicts of interest in this paper.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.