A radio labeling of a graph \( G \) is a mapping \( f : V(G) \to \{0, 1, 2, \dots\} \) such that \( |f(u)-f(v)| \geq \text{diam}(G) + 1 – d(u,v) \) for every pair of distinct vertices \( u,v \) of \( G \), where \( \text{diam}(G) \) is the diameter of \( G \) and \( d(u,v) \) is the distance between \( u \) and \( v \) in \( G \). The radio number \( \text{rn}(G) \) of \( G \) is the smallest integer \( k \) such that \( G \) admits a radio labeling \( f \) with \( \max\{f(v) : v \in V(G)\} = k \). In this paper, we give a lower bound for the radio number of the Cartesian product of a tree and a complete graph and give two necessary and sufficient conditions for the sharpness of the lower bound. We also give three sufficient conditions for the sharpness of the lower bound. We determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph which attains the lower bound. The radio number of the Cartesian product of a path and a complete graph derived in [B. M. Kim, W. Hwang, and B. C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim., 30 (2015), 139–149] can be obtained using our results in a short way.
The channel assignment problem is the problem of assigning a channel to each transmitter in a radio network such that a set of constraints is satisfied and the span is minimized. The constraints for assigning channels to transmitters are usually determined by the geographic location of the transmitters; the closer the location, the stronger the interference might occur. In order to avoid stronger interference, the larger frequency gap between two assigned frequencies must be required. In [10], Hale designed the optimal labelling problem for graphs to deal with this channel assignment problem. In this model, the transmitters are represented by the vertices of a graph, and two vertices are adjacent if the corresponding transmitters are close to each other. Initially, only two levels of interference, namely avoidable and unavoidable, were considered which inspired Griggs and Yeh [8] to introduce the following concept: An \(L(2,1)\)-labelling of a graph \(G\) is a function \(f : V(G) \rightarrow \{0, 1, 2, \ldots\}\) such that \(|f(u)-f(v)| \geq 2\) if \(d(u,v) = 1\) and \(|f(u)-f(v)| \geq 1\) if \(d(u,v) = 2\). The span of \(f\) is defined as \(\max\{|f(u)-f(v)|: u, v \in V(G)\}\), and the \(\lambda\)-number (or the \(\lambda_{2,1}\)-number) of \(G\) is the minimum span of an \(L(2,1)\)-labelling of \(G\). The \(L(2,1)\)-labelling problem has been studied extensively in the past more than two decades, as one can find in the survey articles [5,19].
Denote the diameter of a graph \(G\) by \({\rm diam}(G)\) (the diameter of a graph \(G\) is \({\rm diam}(G) = \max\{d(u,v) : u, v \in V(G)\}\)). In [7,6], Chartrand et al. introduced the concept of the radio labelling problem by extending the condition on distance in \(L(2,1)\)-labelling from two to the maximum possible distance in a graph, namely the diameter of a graph.
Observe that the radio labelling problem is a min-max type optimization problem. Without loss of generality, we may always assume that any radio labelling assigns \(0\) to some vertex so that the span of a radio labelling is equal to the maximum label used. Since \(d(u,v) \leq {\rm diam}(G)\), any radio labelling always assigns different labels to distinct vertices. Therefore, a radio labelling \(f\) of graph \(G\) with order \(m\) induces the linear order \[\label{eqn:ord} \vec{V}_f : a_{0}, a_{1}, \ldots, a_{m-1}, \tag{2}\] of the vertices of \(G\) such that \[\label{eq:spf} 0 = f(a_{0}) < f(a_{1}) < \cdots < f(a_{m-1}) = {\rm span}(f). \tag{3}\] A linear order \(a_0,a_1,\ldots,a_{m-1}\) of \(V(T)\) is called an optimal linear order if it induced by some optimal radio labelling \(f\) of \(T\).
Determining the radio number of graphs is a tough and challenging task. The radio number is known only for very few graphs and much attention has been paid to special families of graphs. It turns out that even for some special graph families the problem may be difficult. For example, the radio number of paths was determined by Liu and Zhu in [17], and even for this basic graph family the problem is nontrivial. In [15,16], Liu and Xie determine the radio number for the square graph of paths and cycles. In [4], Benson et al. determined the radio number of all graphs of order \(n \ge 2\) and diameter \(n-2\). In [13], Liu gave a lower bound for the radio number of trees and a necessary and sufficient condition for this bound to be achieved. The author also presented a special class of trees, namely spiders, achieving this lower bound. In [12], Li et al. determined the radio number of complete \(m\)-ary trees of height \(k\), for \(k \geq 1, m \geq 2\). In [9], Halász and Tuza gave a lower bound for the radio number of level-wise regular trees and proved further that this bound is tight when all the internal vertices have degree more than three. In [3], Bantva et al. gave a necessary and sufficient condition for the lower bound given in [13] to be tight along with two sufficient conditions for achieving this lower bound. Using these results, they also determined the radio number of three families of trees in [3]. In [1], Bantva determined the radio number of some trees obtained by applying a graph operation on given trees. In [14], Liu et al. improved the lower bound for the radio number of trees. Recently, in [2], Bantva and Liu gave a lower bound for the radio number of block graphs and, three necessary and sufficient conditions for achieving the lower bound. The authors gave three other sufficient conditions for achieving the lower bound and also discuss the radio number of line graphs of trees and block graphs in [2]. Using these results, the authors determine the radio number of extended star of blocks and level-wise regular block graphs in [2].
In this paper, we give a lower bound for the radio number of the Cartesian product of a path and a complete graph (Theorem 3.1). We also give two necessary and sufficient conditions (Theorems 3.2 and 3.3) and three other sufficient conditions (Theorem 3.4) for achieving the lower bound. Using these results, we determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph. The radio number of the Cartesian product of a path and a complete graph given in [11] can be obtained using our results in a short way.
We follow [17] for standard graph-theoretic terms and notations. In a graph \(G\), the neighbourhood of any \(v \in V(G)\) is \(N_G(v) = \{u : u \mbox{ is adjacent to }v\}\). The distance between two vertices \(u\) and \(v\) in \(G\), denoted by \(d_G(u,v)\), is the length of the shortest path joining \(u\) and \(v\) in \(G\). The diameter of a graph \(G\), denoted by \({\rm diam}(G)\), is \({\rm diam}(G) = \max\{d_G(u,v) : u, v \in V(G)\}\). We drop the suffix in above-defined terms when \(G\) is clear in the context. A complete graph \(K_n\) is a graph on \(n\) vertices in which any two vertices are adjacent. A tree is a connected acyclic graph. We fix \(V(T) = \{u_0,u_1,\ldots,u_{m-1}\}\) for tree \(T\) of order \(m\) and \(V(K_n) = \{v_0,v_1,\ldots,v_{n-1}\}\) throughout the paper. A vertex \(v \in V(T)\) is an internal vertex of \(T\) if it has degree greater than one and is a leaf otherwise. In [3,13], the weight of \(T\) from \(v \in V(T)\) is defined as \[w_{T}(v) = \sum\limits_{u \in V(T)}d(u,v),\] and the weight of \(T\) is defined as \[w(T) = \min\{w_{T}(v) : v \in V(T)\}.\] A vertex \(v \in V(T)\) is a weight center [3,13] of \(T\) if \(w_{T}(v) = w(T)\). Denote by \(W(T)\) the set of weight centers of \(T\). In [13], the following is proved about \(W(T)\).
A vertex \(u\) is called [3,13] an ancestor of a vertex \(v\), or \(v\) is a descendent of \(u\), if \(u\) is on the unique path joining a weight center and \(v\). Let \(u \in V(T) \setminus W(T)\) be a vertex adjacent to a weight center \(x\). The subtree of \(T\) induced by \(u\) and all its descendants is called the branch of \(T\) at \(u\). Two vertices \(u, v\) of \(T\) are said to be in different branches if the path between them contains only one weight center and in opposite branches if the path joining them contains two weight centers. We view a tree \(T\) rooted at its weight center \(W(T)\): if \(W(T) = \{r\}\), then \(T\) is rooted at \(r\); if \(W(T) = \{r,r'\}\), then \(T\) is rooted at \(r\) and \(r'\) in the sense that both \(r\) and \(r'\) are at level 0. In either case, for each \(u \in V(T)\), define \[L(u) = \mbox{min}\{d(u,x) : x \in W(T)\},\] to indicate the level of \(u\) in \(T\), and define \[L(T) = \sum\limits_{u \in V(T)} L(u),\] the total level of \(T\). For any \(u, v \in V(T)\), define \[\label{eq:phi} \phi(u,v) = \mbox{max}\{L(x) : x \mbox{ is a common ancestor of $u$ and $v$}\},\] \[\label{eq:delta} \delta(u,v) = \begin{cases} 1, & \mbox{if $|W(T)| = 2$ and the $(u, v)$-path in $T$ contains both weight centers}, \\ 0, & \mbox{otherwise}. \end{cases}\]
(a) \(\phi(u,v) \geq 0\);
(b) \(\phi(u,v) = 0\) if and only if \(u\) and \(v\) are in different or opposite branches;
(c) \(\delta(u,v) = 1\) if and only if \(T\) has two weight centers and \(u\) and \(v\) are in opposite branches;
(d) the distance \(d(u,v)\) in \(T\) between \(u\) and \(v\) can be expressed as
\[\label{eqn:dist} d(u,v) = L(u) + L(v) – 2\phi(u,v)+\delta(u,v). \tag{4}\]
Define \[\varepsilon(T) = \begin{cases} 1, & \mbox{if $|W(T)| = 1$}, \\ 0, & \mbox{if $|W(T)| = 2$}. \end{cases}\]
Let \(G=(V(G),E(G))\) and \(H=(V(H),E(H))\) be two graphs. The Cartesian product of \(G\) and \(H\) is the graph \(G \Box H\) with \(V(G \Box H) = V(G) \times V(H)\) such that two vertices \((a,b)\) and \((c,d)\) are adjacent if \(a=c\) and \((b,d) \in E(H)\) or \(b=d\) and \((a,c) \in E(G)\). It is clear from the definition that \(d_{G \Box H} ((x_1, y_1), (x_2, y_2)) = d_{G} (x_1, x_2) + d_{H} (y_1, y_2)\).
(a) \(|V(T \Box K_n)| = mn\), and
(b) \({\rm diam}(T \Box K_n) = {\rm diam}(T)+1\).
Let \(\vec{V} = (w_0,w_1,\ldots,w_{mn-1})\) be an ordering of \(V(T \Box K_n)\), where \(|T| = m\). Then each \(w_t\; (0 \leq t \leq mn-1)\) is an ordered pair \((u_{i_t},v_{j_t})\) with \(u_{i_t} \in V(T)\) and \(v_{j_t} \in V(K_n)\). Hence each vertex \(u_i,\;i=0,1,\ldots,m-1\) appears \(n\) times and each vertex \(v_j,\;j=0,1,\ldots,n-1\) appears \(m\) times in \(T \Box K_n\). For \(w_a = (u_{i_a},v_{j_a}), w_b = (u_{i_b},v_{j_b}) \in V(T \Box K_n)\;(0 \leq a,b \leq mn-1)\), \(v_{j_a}\) and \(v_{j_b}\) are called distinct if \(j_a \neq j_b\). For any \(w_a = (u_{i_a},v_{j_a}), w_b = (u_{i_b},v_{j_b}) \in V(T \Box K_n)\;(0 \leq a,b \leq mn-1)\), the distance between \(w_a\) and \(w_b\) is given by \[\label{dist:TKn} d(w_a,w_b) = L(u_{i_a})+L(u_{i_b})+\delta(u_{i_a},u_{i_b})-2\phi(u_{i_a},u_{i_b})+d(v_{j_a},v_{j_b}). \tag{5}\]
In this section, we continue to use terms and notations defined in the previous section. We first give a lower bound for the radio number of the Cartesian product of a tree and a complete graph. Next we give two necessary and sufficient conditions and three other sufficient conditions for achieving the lower bound.
Proof. It is enough to prove that any radio labelling of \(T \Box K_n\) has no span less than that of the right-hand side of (6). Suppose \(f\) is any radio labelling of \(T \Box K_n\) which induces an ordering \(\vec{V}_f = (w_0,w_1,\ldots,w_{mn-1})\) such that \(0 = f(w_0) < f(w_1) < \cdots < f(w_{mn-1})\). Denote \({\rm diam}(T \Box K_n)=d'\). By the definition of a radio labelling, \(f(w_{t+1})-f(w_t) \geq d'+1-d(w_t,w_{t+1})\) for \(0 \leq t \leq mn-2\). Since \(d' = d+1\) by Observation 2.4, we have \(f(w_{t+1})-f(w_t) \geq d+2-d(w_t,w_{t+1})\) for \(0 \leq t \leq mn-2\). Summing up these \(mn-1\) inequalities, we obtain \[\label{eqn:spn1} {\rm span}(f) = f(w_{mn-1}) \geq (mn-1)(d+2)-\sum\limits_{t=0}^{mn-2}d(w_t,w_{t+1}). \tag{7}\]
Case 1. \(|W(T)|=1\). In this case, \(\delta(u_{i_t},u_{i_{t+1}}) = 0\) by the definition of \(\delta\), \(\phi(u_{i_t},u_{i_{t+1}}) \geq 0\) and \(0 \leq d(v_{j_t},v_{j_{t+1}}) \leq 1\) for all \(0 \leq t \leq mn-2\). Hence, using (5), we obtain \[\begin{aligned} \sum\limits_{t=0}^{mn-2}d(w_t,w_{t+1}) =& \sum\limits_{t=0}^{mn-2}[L(u_{i_t})+L(u_{i_{t+1}})-2\phi(u_{i_t},u_{i_{t+1}})+d(v_{j_t},v_{j_{t+1}})] \\ \leq & \sum\limits_{t=0}^{mn-2}[L(u_{i_t})+L(u_{i_{t+1}})+d(v_{j_t},v_{j_{t+1}})] \\ \leq & 2n\sum\limits_{i=0}^{m-1}L(u_i)+(mn-1)-L(u_{i_0})-L(u_{i_{mn-1}}) \\ \leq & 2nL(T)+mn-1. \end{aligned}\] Substituting this into (7), we have \({\rm span}(f) \geq (mn-1)(d+1)-2nL(T)\).
Case 2. \(|W(T)|=2\). In this case, \(0 \leq \delta(u_{i_t},u_{i_{t+1}}) \leq 1\), \(\phi(u_{i_t},u_{i_{t+1}}) \geq 0\) and \(0 \leq d(v_{j_t},v_{j_{t+1}}) \leq 1\) for all \(0 \leq t \leq mn-2\). Hence, using (5), we obtain \[\begin{aligned} \sum\limits_{t=0}^{mn-2}d(w_t,w_{t+1}) =& \sum\limits_{t=0}^{mn-2}[L(u_{i_t})+L(u_{i_{t+1}})+\delta(u_{i_t},u_{i_{t+1}})-2\phi(u_{i_t},u_{i_{t+1}})\\ & +d(v_{j_t},v_{j_{t+1}})] \\ \leq & \sum\limits_{t=0}^{mn-2}[L(u_{i_t})+L(u_{i_{t+1}})+1+d(v_{j_t},v_{j_{t+1}})] \\ \leq & 2n\sum\limits_{i=0}^{m-1}L(u_i)+(mn-1)+(mn-1)-L(u_{i_0})-L(u_{i_{mn-1}}) \\ \leq & 2nL(T)+2(mn-1). \end{aligned}\] Substituting this into (7), we have \({\rm span}(f) \geq (mn-1)d-2nL(T)\). ◻
(a) \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0\);
(b) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for all \(0 \leq t \leq mn-2\);
(c) for \(w_a = (u_{i_a},v_{j_a}), w_b = (u_{i_b},v_{j_b})\,(0 \leq a < b \leq mn-1)\), the distance between any two vertices \(u_{i_a}\) and \(u_{i_b}\) satisfies
\[\label{eqn:dab} d(u_{i_a},u_{i_b}) \geq \sum\limits_{t=a}^{b-1}[L(u_{i_t})+L(u_{i_{t+1}})-(d+\varepsilon)]+(d+1). \tag{9}\]
Moreover, under these conditions (a)-(c), the mapping \(f\) defined by \[\label{eqn:f00} f(w_0) = 0, \tag{10}\] \[\label{eqn:f11} f(w_{t+1}) = f(w_t)+d+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}}), 0 \leq t \leq mn-2, \tag{11}\] is an optimal radio labelling of \(T \Box K_n\).
Proof. Necessity. Suppose that (8) holds. Note that (8) holds if equality hold in (1) and everywhere in the proof of Theorem 3.1. Again observe that if the equality holds everywhere in the proof of Theorem 3.1 then an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T \Box K_n)\) induced by \(f\) satisfies the followings: (1) \(L(u_{i_0})= L(u_{i_{mn-1}})=0\), (2) \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches when \(|W(T)|=1\) and in opposite branches when \(|W(T)|=2\) for all \(0 \leq t \leq mn-2\), (3) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for all \(0 \leq t \leq mn-2\). Hence in this case the definition of radio labelling \(f\) can be written as \(f(w_0) = 0\) and \(f(w_{t+1}) = f(w_t)+d'+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}})-1 = f(w_t)+d+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}})\) for \(0 \leq t \leq mn-2\), where \(d' = {\rm diam}(T \Box K_n)\). Summing this last equality for \(w_a\) to \(w_b\,(0 \leq a < b \leq mn-1)\), we obtain \[f(w_b)-f(w_a) = \sum\limits_{t=a}^{b-1}[d+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}})].\]
Since \(f\) is a radio labelling of \(T \Box K_n\), we have \(f(w_b)-f(w_a) \geq d'+1-d(w_a,w_b) = d+2-d(w_a,w_b)\). Also note that \(d(w_a,w_b) = d(u_{i_a},u_{i_b})+1\) by (5). Substituting these into the above equation, we obtain \[d(u_{i_a},u_{i_b}) \geq \sum\limits_{t=a}^{b-1}[L(u_{i_t})+L(u_{i_{t+1}})-(d+\varepsilon)]+(d+1).\]
Sufficiency. Suppose there exists an ordering (\(w_0\), \(w_1\), \(\ldots\), \(w_{mn-1}\)) of \(V(T \Box K_n)\) satisfies the conditions (a)-(c) and \(f\) is defined by (10) and (11). Note that it is enough to prove that \(f\) is a radio labelling of \(T \Box K_n\) and the span of \(f\) is the right-hand side of (8). Denote \({\rm diam}(T \Box K_n) = d'\). Let \(w_a\) and \(w_b\;(0 \leq a < b \leq mn-1)\) be two arbitrary vertices. \[\begin{aligned} % \nonumber % Remove numbering (before each equation) f(w_b)-f(w_a) =& \sum\limits_{t=a}^{b-1}(f(w_{t+1})-f(w_t)), \\ =& \sum\limits_{t=a}^{b-1}(d+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}})), \\ =& d+1-d(u_{i_a},u_{i_b}), \\ =& d+2-(d(u_{i_a},u_{i_b})+1), \\ =& d'+1-d(w_a,w_b). \end{aligned}\] The span of \(f\) is \[\begin{aligned} % \nonumber % Remove numbering (before each equation) {\rm span}(f) =& f(w_{mn-1})-f(w_0), \\ =& \sum\limits_{t=0}^{mn-2}(f(w_{t+1})-f(w_t)), \\ =& \sum\limits_{t=0}^{mn-2}(d+\varepsilon-L(u_{i_t})-L(u_{i_{t+1}})), \\ =& (mn-1)(d+\varepsilon)-2\sum\limits_{t=0}^{mn-1}L(u_{i_t})+L(u_{i_0})+L(u_{i_{mn-1}}), \\ =& (mn-1)(d+\varepsilon)-2nL(T). \end{aligned}\] ◻
(a) \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0\);
(b) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for \(0 \leq t \leq mn-2\);
(c) \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches when \(|W(T)|=1\) and in opposite branches when \(|W(T)|=2\) for \(0 \leq t \leq mn-2\);
(d) \(L(u_{i_t}) \leq (d+1)/2\) when \(|W(T)|=1\) and \(L(u_{i_t}) \leq (d-1)/2\) when \(|W(T)|=2\) for all \(0 \leq t \leq mn-1\);
(e) for any \(w_a = (u_{i_a},v_{j_a}), w_b = (u_{i_b},v_{j_b})\,(0 \leq a < b \leq mn-1)\) such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\), \(u_{i_a}\) and \(u_{i_b}\) satisfy \[\label{phiab} \phi(u_{i_a},u_{i_b}) \leq \left(\frac{b-a-1}{2}\right)(d+\varepsilon)-\sum\limits_{t=a+1}^{b-1}L(u_{i_t})-\left(\frac{1-\varepsilon}{2}\right). \tag{13}\]
Proof. Necessity. Suppose (12) holds. Then there exists an ordering (\(w_0\), \(w_1\), \(\ldots\), \(w_{mn-1}\)) of \(T \Box K_n\) such that the conditions (a)-(c) of Theorem 3.2 holds. Hence the conditions (a) and (b) are satisfied. Taking \(a=t\) and \(b=t+1\) in (9), we obtain \(d(w_t,w_{t+1}) = d(u_{i_t},u_{i_{t+1}})+d(v_{j_t},v_{j_{t+1}}) = L(u_{i_t})+L(u_{i_{t+1}})+1-\varepsilon+1\). Hence we have \(d(u_{i_t},u_{i_{t+1}}) = L(u_{i_t})+L(u_{i_{t+1}})+1-\varepsilon\) for all \(0 \leq t \leq mn-2\) as \(0 \leq d(u_{i_t},u_{i_{t+1}}) \leq L(u_{i_t})+L(u_{i_{t+1}})+1-\varepsilon\) and \(0 \leq d(v_{j_t},v_{j_{t+1}}) \leq 1\). Therefore, by Lemma 2.3, \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches when \(|W(T)|=1\) and in opposite branches when \(|W(T)|=2\) for all \(0 \leq t \leq mn-2\). Hence the condition (c) is satisfied. Since \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0\), it is clear that \(L(u_{i_t}) < (d+1)/2\) for \(t=0,mn-1\). For \(1 \leq t \leq mn-2\), considering \(u_{i_{t-1}}\) and \(u_{i_{t+1}}\) in (9) and using (5), we obtain \[2L(u_{i_t}) \leq (d+\varepsilon)-(1-\varepsilon)+\delta(u_{i_{t-1}},u_{i_{t+1}})-2\phi(u_{i_{t-1}},u_{i_{t+1}}).\]
In above equation, observe that when \(|W(T)|=1\) then \(\delta(u_{i_{t-1}},u_{i_{t+1}})=0\) by the definition of \(\delta\) and when \(|W(T)|=2\) then \(u_{i_{t-1}}\) and \(u_{i_{t+1}}\) are in different or in the same branch of \(T\) and hence \(\delta(u_{i_{t-1}},u_{i_{t+1}})=0\). Thus we have \[2L(u_{i_t}) \leq d+2\varepsilon-1.\]
Hence, the condition (d) is satisfied. To prove (e), let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}) (0 \leq a < b \leq mn-1)\) be such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\). Then \(\delta(u_{i_a},u_{i_b})=0\). Using (5) in (9), (13) can be obtained easily from (9).
Sufficiency. Suppose there exists an ordering \((w_0,w_1,\ldots,w_{mn-1})\) of \(V(T \Box K_n)\) such that conditions (a)-(e) hold. To prove (12) holds, we show that an ordering \(w_0,w_1,\ldots,w_{mn-1}\) satisfies the conditions (a)-(c) of Theorem 3.2. Since the conditions (a) and (b) are identical with the conditions (a) and (b) of Theorem 3.2, we need to prove the condition (9) only. Denote the right-hand side of (9) by \(S_{a,b}\). Let \(w_a = (u_{i_a},v_{j_a}), w_b = (u_{i_b},v_{j_b})\; (0 \leq a < b \leq mn-1)\) be any two vertices. If \(u_{i_a}\) and \(u_{i_b}\) are in opposite branches, then \(d(u_{i_a},u_{i_b}) = L(u_{i_a})+L(u_{i_b})+1\). Hence, \(S_{a,b} = L(u_{i_a})+L(u_{i_b})+2\sum\limits_{t=a+1}^{b-1}L(u_{i_t})-(b-a)d\)\(+d+1 \leq L(u_{i_a})+L(u_{i_b})+1+2(b-a-1)((d-1)/2)-(b-a-1)d = L(u_{i_a})+L(u_{i_b})+1-(b-a-1) \leq \)\(L(u_{i_a})+L(u_{i_b})+1 = d(u_{i_a},u_{i_b})\). If \(u_{i_a}\) and \(u_{i_b}\) are in different branches, then \(d(u_{i_a},u_{i_b}) = L(u_{i_a})+L(u_{i_b})\) and \(S_{a,b} = L(u_{i_a})+L(u_{i_b})+2\sum\limits_{t=a+1}^{b-1}L(u_{i_t})-(b-a-1)(d+\varepsilon)+(1-\varepsilon)\). If \(|W(T)|=1\), then note that \(L(u_{i_t}) \leq (d+1)/2\) for all \(0 \leq t \leq mn-1\) and hence \(S_{a,b} \leq L(u_{i_a})+L(u_{i_b})+2(b-a-1)((d+1)/2)-(b-a-1)(d+1) = L(u_{i_a})+L(u_{i_b}) = d(u_{i_a},u_{i_b})\). If \(|W(T)|=2\), then note that \(b-a-1 \geq 1\) and \(L(u_{i_t}) \leq (d-1)/2\) for all \(0 \leq t \leq mn-1\) and hence \(S_{a,b} \leq L(u_{i_a})+L(u_{i_b})+2(b-a-1)((d-1)/2)-(b-a-1)d+1 = L(u_{i_a})+L(u_{i_b})+1-(b-a-a) \)\(\leq L(u_{i_a})+L(u_{i_b}) = d(u_{i_a},u_{i_b})\). If \(u_{i_a}\) and \(u_{i_b}\) are in the same branch, then (9) can be obtained easily using (13). This completes the proof. ◻
(a) \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0\),
(b) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for all \(0 \leq t \leq mn-2\),
(c) \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches when \(|W(T)|=1\) and in opposite branches when \(|W(T)|=2\) for all \(0 \leq t \leq mn-2\),
and one of the following holds:
(d) \(\min\{d(u_{i_t},u_{i_{t+1}}),d(u_{i_{t+1}},u_{i_{t+2}})\} \leq (d+1-\varepsilon)/2\) for all \(0 \leq t \leq mn-3\);
(e) \(d(u_{i_t},u_{i_{t+1}}) \leq (d+1+\varepsilon)/2\) for all \(0 \leq t \leq mn-2\);
(f) for all \(0 \leq t \leq mn-1\), \(L(u_{i_t}) \leq (d+1)/2\) when \(|W(T)|=1\) and \(L(u_{i_t}) \leq (d-1)/2\) when \(|W(T)|=2\) and, if \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}) (0 \leq a < b \leq mn-1)\) such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\) then \(b-a \geq d\).
Proof. We show that if (a)-(c) and one of (d)-(f) holds for an ordering \(w_0,w_1,\ldots,w_{mn-1}\) such that \(w_t = (u_{i_t},v_{j_t}), 0 \leq t \leq mn-1\), then (a)-(e) of Theorem 3.3 are satisfied. Since the conditions (a)-(c) are identical in both Theorems 3.3 and 3.4, we need to verify the conditions (d) and (e) of Theorem 3.3 only. Denote the right-hand side of (13) by \(P_{a,b}\). We consider the following two cases.
Case 1. \(|W(T)|=1\). In this case, recall that \(\varepsilon= 1\) and \(\delta(u_{i_t},u_{i_{t+1}}) = 0\) for all \(0 \leq t \leq mn-2\) by the definition of \(\delta\).
Subcase 1.1. Suppose (a)-(d) hold. It is clear that \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0 \leq (d+1)/2\) and for \(1 \leq t \leq mn-2\), \(L(u_{i_t}) \leq \min\{d(u_{i_t},u_{i_{t+1}}),d(u_{i_{t+1}},u_{i_{t+2}})\} \leq d/2 < (d+1)/2\). Let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}),\; 0 \leq a < b \leq mn-1\) be two arbitrary vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\). If \(b-a \geq 4\), then \(P_{a,b} \geq 3(d+1)/2-d/2-(d+1)/2 = d/2+1 \geq \phi(u_{i_a},u_{i_b})\). Assume \(b-a=3\). If \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) \leq d/2\), then \(P_{a,b} \geq (d+1)-d/2 = d/2+1 \geq \phi(u_{i_a},u_{i_b})\). If \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) > d/2\), then \(L(u_{i_{a+2}})+L(u_{i_{a+3}}) \leq d/2\) and hence \(L(u_{i_{a+2}}) \leq d/2-L(u_{i_{a+3}})\). Therefore, \(P_{a,b} \geq d+1-L(u_{i_{a+1}})-L(u_{i_{a+2}}) \geq d+1-(d+1)/2-d/2+L(u_{i_{a+3}}) = L(u_{i_{a+3}})+1/2 \geq \phi(u_{i_a},u_{i_b})\). Assume \(b-a = 2\). Then either \(L(u_{i_a})+L(u_{i_{a+1}}) \leq d/2\) or \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) \leq d/2\). Without loss of generality, we may assume that \(L(u_{i_a})+L(u_{i_{a+1}}) \leq d/2\). Then \(L(u_{i_{a+1}}) \leq d/2-L(u_{i_a})\). Hence, \(P_{a,b} = (d+1)/2-L(u_{i_{a+1}}) \geq (d+1)/2-d/2+L(u_{i_a}) = L(u_{i_a})+(1/2) \geq \phi(u_{i_a},u_{i_b})\).
Subcase 1.2. Suppose (a)-(c) and (e) hold. Note that \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0 \leq (d+1)/2\). Since \(L(u_{i_t}) \geq 1\) and \(L(u_{i_t})+L(u_{i_{t+1}}) = d(u_{i_t},u_{i_{t+1}}) \leq (d+2)/2\) for \(0 \leq t \leq mn-1\), we obtain \(L(u_{i_t}) \leq (d+1)/2\) for all \(0 \leq t \leq mn-1\).
Let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}), 0 \leq a < b \leq mn-1\) be two arbitrary vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\). If \(b-a \geq 3\), then \(P_{a,b} \geq d+1-L(u_{i_{a+1}})-L(u_{i_{a+2}}) \geq d+1-(d+2)/2 = d/2 \geq \phi(u_{i_a},u_{i_b})\). Assume \(b-a = 2\). Note that \(L(u_{i_a})+L(u_{i_{a+1}}) \leq (d+2)/2\) and hence \(L(u_{i_{a+1}}) \leq (d+2)/2-L(u_{i_a})\). Therefore, \(P_{a,b} = (d+1)/2-L(u_{i_{a+1}}) \geq (d+1)/2-((d+2)/2-L(u_{i_a})) = L(u_{i_a})-(1/2) \geq \phi(u_{i_a},u_{i_b})\).
Subcase 1.3. Suppose (a)-(c) and (f) hold. Assume \(d\) is even. Then \(L(u_{i_t}) \leq d/2\) for all \(0 \leq t \leq mn-1\) and hence \(P_{i,j} \geq ((b-a-1)/2)(d+1)-(b-a-1)(d/2) \geq (b-a-1)/2 \geq (d-1)/2 \geq \phi(u_{i_a},u_{i_b})\). Assume \(d\) is odd. Then note that only for one vertex \(u_{i_q}\), \(L(u_{i_q}) = (d+1)/2\) from consecutive \(b-a\) vertices and for all other vertices \(u_{i_t}\), \(L(u_{i_t}) \leq d/2\). Hence, \(P_{a,b} \geq ((b-a-1)/2)(d+1)-(b-a-2)(d/2)-(d+1)/2 \geq (b-a-2)/2 \geq (d-2)/2 \geq \phi(u_{i_a},u_{i_b})\).
Case 2. \(|W(T)|=2\). In this case, recall that \(\varepsilon=0\) and \(\delta(u_{i_t},u_{i_{t+1}}) = 1\) for all \(0 \leq t \leq mn-1\) by the definition of the ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T \Box K_n)\).
Subcase 2.1. Suppose (a)-(d) hold. It is clear that \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0 \leq (d-1)/2\) and for \(1 \leq t \leq mn-2\), \(L(u_{i_t}) \leq \min\{d(u_{i_{t-1}},u_{i_{t}}),d(u_{i_t},u_{i_{t+1}})\}-1 \leq (d+1)/2-1 = (d-1)/2\). Let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}),\, 0 \leq a < b \leq mn-1\) be two arbitrary vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\). If \(b-a \geq 4\), then \(P_{a,b} \geq 3d/2-(d-1)-1/2 = (d+1)/2 \geq \phi(u_{i_a},u_{i_b})\). Assume \(b-a = 3\). If \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) \leq (d-1)/2\), then \(P_{a,b} \geq d-(d-1)/2-1/2 = d/2 \geq \phi(u_{i_a},u_{i_b})\). If \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) > (d-1)/2\), then \(L(u_{i_a})+L(u_{i_{a+1}}) \leq (d-1)/2\) and hence \(L(u_{i_{a+1}}) \leq (d-1)/2-L(u_{i_a})\). Therefore, \(P_{a,b} \geq d-((d-1)/2-L(u_{i_a}))-(d-1)/2-1/2 = L(u_{i_a})+1/2 \geq \phi(u_{i_a},u_{i_b})\). Assume \(b-a = 2\). Then either \(L(u_{i_a})+L(u_{i_{a+1}}) \leq (d-1)/2\) or \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) \leq (d-1)/2\). Without loss of generality, we may assume that \(L(u_{i_{a+1}})+L(u_{i_{a+2}}) \leq (d-1)/2\). Then \(L(u_{i_{a+1}}) \leq (d-1)/2-L(u_{i_{a+2}})\). Hence, \(P_{a,b} = d/2-L(u_{i_{a+1}})-1/2 \geq d/2-((d-1)/2-L(i_{a+2}))-1/2 = L(u_{i_{a+2}}) \geq \phi(u_{i_a},u_{i_b})\).
Subcase 2.2. Suppose (a)-(c) and (e) hold. Note that \(L(u_{i_0}) = L(u_{i_{mn-1}}) = 0 \leq (d-1)/2\). Since \(L(u_{i_t}) \geq 1\) and \(L(u_{i_t})+L(u_{i_{t+1}}) = d(u_{i_t},u_{i_{t+1}})-1 \leq (d+1)/2-1 = (d-1)/2\) for \(0 \leq t \leq mn-1\), we obtain \(L(u_{i_t}) \leq (d-1)/2\) for all \(0 \leq t \leq mn-1\).
Let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b}),\; 0 \leq a < b \leq mn-1\) be two arbitrary vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T\). If \(b-a \geq 3\), then \(P_{a,b} \geq d-L(u_{i_{a+1}})-L(u_{i_{a+2}})-1/2 \geq d-(d-1)/2-1/2 = d/2 \geq \phi(u_{i_a},u_{i_b})\). Assume that \(b-a = 2\). Then note that \(L(u_{i_a})+L(u_{i_{a+1}}) \leq (d-1)/2\) and hence \(L(u_{i_a}) \leq (d-1)/2-L(u_{i_{a+1}})\). Hence, \(P_{a,b} \geq d/2-L(u_{i_t})-(1/2) \geq d/2-[(d-1)/2-L(u_{i_{a+1}})]-(1/2) = L(u_{i_{a+1}}) \geq \phi(u_{i_a},u_{i_b})\).
Subcase 2.3. Suppose (a)-(c) and (f) hold. Assume \(d\) is even. Then \(L(u_{i_t}) \leq (d-2)/2\) for all \(0 \leq t \leq mn-1\) and hence \(P_{a,b} \geq ((b-a-1)/2)d-(b-a-1)((d-2)/2)-1/2 = b-a-(3/2) \geq d-(3/2) \geq \phi(u_{i_a},u_{i_b})\). Assume \(d\) is odd. Then note that only for one vertex \(u_{i_q}\), \(L(u_{i_q}) \leq (d-1)/2\) from \(b-a\) consecutive vertices and for all other vertices \(u_{i_t}\), \(L(u_{i_t}) \leq (d-3)/2\). Hence, \(P_{a,b} \geq ((b-a-1)/2)d-(b-a-2)((d-3)/2)-(d-1)/2-(1/2) = 3(b-a-2)/2 \geq 3(d-2)/2 \geq \phi(u_{i_a},u_{i_b})\). ◻
In this section, using the results in Section 3, we determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph.
It is well known that the center of tree \(T\) consists of one vertex \(r\) or two adjacent vertices \(r,r'\) depending on \({\rm diam}(T)\) is even or odd. We view a tree \(T\) rooted at \(r\) or at both \(r,r'\) respectively. Halász and Tuza [9] defined a level-wise regular tree to be a tree \(T\) in which all vertices at distance \(i\) from root \(r\) or \(\{r,r'\}\) have the same degree, say, \(d_i\) for \(0 \leq i \leq h\), where \(h\) (the largest distance from a vertex to the root) is the height of tree \(T\). Note that a level-wise regular tree is determined by its center(s) and \((d_0,d_1,\ldots,d_{h-1})\). Denote the level-wise regular tree by \(T^z = T^z_{d_0,d_1,\ldots,d_{h-1}}\), where \(z\) denotes the number of roots of the level-wise regular tree. A star \(K_{1,q}\) is a tree consisting of \(q\) leaves and another vertex joined to all leaves by edges. A double star \(D_q\) is a graph obtained by joining the center vertices of two copies of star graph \(K_{1,q}\) by an edge. A banana tree \(B_{q,k}\) is a graph constructed by connecting a single leaf from \(q\) distinct copies of a star \(K_{1,k}\) with a single vertex that is distinct from all the vertices of the star graphs. Note that \(K_{1,q}\), \(D_q\) and \(B_{q,k}\) are level-wise regular trees \(T^1_q\), \(T^2_{q+1}\) and \(T^1_{q,2,k}\), respectively.
Proof. The order of \(T^z\), \(L(T^z)\) and diameter \(d\) of \(T^z\) are given by \[|V(T^z)| = \begin{cases} 1+d_0+d_0\displaystyle\sum\limits_{i=1}^{h-1}\left(\displaystyle\prod_{1 \leq j \leq i}(d_j-1)\right), & \mbox{if $z = 1$}, \\ 2+2\displaystyle\sum\limits_{i=0}^{h-1}\left(\displaystyle\prod_{0 \leq j \leq i}(d_j-1)\right), & \mbox{if $z = 2$}, \end{cases}\]
\[L(T^z) = \begin{cases} d_0+d_0\displaystyle\sum\limits_{i=1}^{h-1}(i+1)\left(\displaystyle\prod_{1 \leq j \leq i}(d_j-1)\right), & \mbox{if $z = 1$}, \\ 2\displaystyle\sum\limits_{i=0}^{h-1}(i+1)\left(\displaystyle\prod_{0 \leq j \leq i}(d_j-1)\right), & \mbox{if $z = 2$}, \end{cases}\]
\[d = \begin{cases} 2h, & \mbox{if $z = 1$}, \\ 2h+1, & \mbox{if $z = 2$}. \end{cases}\] Substituting the above into (6), we obtain the right-hand side of (15) as a lower bound for \({\rm rn}(T^z \Box K_n)\). We now prove that this lower bound is tight by giving an ordering of \(V(T^z \Box K_n)\) which satisfies the conditions in Theorem 3.2. For this purpose, denote \(V(K_n) = \{v_0,v_1,\ldots,v_{n-1}\}\) and \(V(T^z) = \{u_0,u_1,\ldots,u_{m-1}\}\) such that the ordering \(u_0,u_1,\ldots,u_{n-1}\) is obtained as follows.
Case 1. \(z=1\).
In this case, let \(r\) be the unique center of \(T^1\). Denote \(d_0\) children of \(r\) by \(r_0,\ldots,r_{d_0-1}\). For \(0 \leq i \leq d_0-1\), denote \(d_1-1\) children of \(r_i\) by \(r_{i,0},r_{i,1},\ldots,r_{i,d_1-1}\). Inductively, denote the \(d_{l}-1\) children of \(r_{i_1,i_2,\ldots,i_l}\;(0 \leq i_1 \leq d_0-1, 0 \leq i_2 \leq d_1-1,\ldots,0 \leq i_l \leq d_{l-1}-1)\) by \(r_{i_1,i_2,\ldots,i_l,i_{l+1}}\), where \(0 \leq i_{l+1} \leq d_l-1\). Continue this process until all the vertices of \(T^1\) get indexed. Now obtain an ordering \(u_0,u_1,\ldots,u_{m-1}\) of vertices of \(T^1\) as follows: Set \(u_0 := r\) and for \(1 \leq t \leq m-1\), set \(u_t := r_{i_1,i_2,\ldots,i_l}\), where \(j=1+i_1+i_2d_0+\cdots+i_ld_0(d_1-1)\cdots(d_l-1)+\displaystyle\sum\limits_{l+1 \leq t \leq h}d_0(d_1-1)\cdots(d_t-1)\).
Case-2. \(z=2\).
In this case, let \(r\) and \(r'\) be two centers of \(T^2\). Denote \(d_0-1\) children of \(r\) and \(r'\) by \(r_0,r_1,\ldots,r_{d_0-2}\) and \(r'_{0},r'_{1},\ldots,r'_{d_0-2}\), respectively. For \(0 \leq i \leq d_0-2\), denote \(d_1-1\) children of \(r_i\) and \(r'_i\) by \(r_{i,0},r_{i,1},\ldots,r_{i,d_1-1}\) and \(r'_{i,0},r'_{i,1},\ldots,r'_{i,d_1-1}\), respectively. Inductively, denote the \(d_l-1\) children of \(r_{i_1,i_2,\ldots,i_l}\) and \(r'_{i_1,i_2,\ldots,i_l}\), where \(0 \leq i_1 \leq d_0-2, 0 \leq i_2 \leq d_1-1,\ldots,0 \leq i_l \leq d_{l-1}-1\) by \(r_{i_1,i_2,\ldots,i_l,i_{l+1}}\) and \(r'_{i_1,i_2,\ldots,i_l,i_{l+1}}\) respectively, where \(0 \leq i_{l+1} \leq d_l-1\). Continue this process until all the vertices of \(T^2\) are indexed. Rename \(x_j := r_{i_1,i_2,\ldots,i_l} \mbox{ and } x'_j := r'_{i_1,i_2,\ldots,i_l}\), where \(j = 1+i_1+i_2(d_0-1)+\cdots+i_l(d_0-1)(d_1-1)\cdots(d_l-1)+\displaystyle\sum\limits_{l+1 \leq t \leq h}(d_0-1)(d_1-1)\cdots(d_t-1)\). Now obtain an ordering \(u_0,u_1,\ldots,u_{m-1}\) as follows: Set \(u_0 := r, u_{m-1} := r'\) and for \(1 \leq t \leq m-2\), set \[u_t := \begin{cases} x_{t/2}, & \mbox{if $t \equiv 0$ (mod $2$)}, \\ x'_{(t+1)/2}, & \mbox{if $t \equiv 1$ (mod $2$)}. \end{cases}\]
We now consider the following two cases to give an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T \Box K_n) = \{(u_i,v_j) : i = 0, 1, \ldots, m-1, j = 0, 1, \ldots, n-1\}\).
Case 1. \(|W(T)|=1\).
We consider the following two subcases to define an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T^1 \Box K_n)\).
Subcase 1. \(|V(T^1)| \leq |V(K_n)|\).
In this case, for \(0 \leq t \leq mn-1\), define \(w_t := (u_i,v_j)\), where \(i \in \{0,1,\ldots,m-1\}\; j \in \{0,1,\ldots,n-1\}\) and \[t := \left\{ \begin{array}{ll} m(j-i)+i & \mbox{if $j \geq i$ and $j-i \neq n-1$}, \\[0.2cm] m(n+j-i)+i & \mbox{if $j<i$ and $i-j \neq 1$}, \\[0.2cm] m(n+j-i)+i-1 & \mbox{if $j < i$ and $i-j = 1$}, \\[0.2cm] mn-1 & \mbox{if $j-i=n-1$}. \\[0.2cm] \end{array} \right.\]
Subcase 2. \(|V(T^1)| > |V(K_n)|\).
In this case, for \(x\mathop{\mathrm{lcm}}(m,n) \leq t \leq (x+1)\mathop{\mathrm{lcm}}(m,n)-1\), where \(0 \leq x \leq \gcd(m,n)-1\), set \[\alpha_t := \left\{ \begin{array}{ll} (u_i,v_{j+x}), & \mbox{if $t \equiv i$ (mod $m$), $t \equiv j$ (mod $n$) and $0\leq j\leq n-(x+1)$}, \\[0.2cm] (u_i,v_{j+x-n}), & \mbox{if $t \equiv i$ (mod $m$), $t \equiv j$ (mod $n$) and $n-x\leq j\leq n-1$}. \end{array} \right.\]
Define an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T^1 \Box K_n)\) as follows: For \(0 \leq t \leq mn-1\), set \[w_t := \left\{ \begin{array}{ll} \alpha_t, & \mbox{if $0 \leq t \leq mn-m-1$}, \\[0.2cm] \alpha_{t+1}, & \mbox{if $mn-m \leq t \leq mn-2$}, \\[0.2cm] \alpha_{mn-m}, & \mbox{if $t = mn-1$}. \end{array} \right.\]
Then, for above defined ordering, it is clear that (a) \(L(u_{i_0}) = L(u_{i_{mn-1}}) = L(u_0) = 0\), (b) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for \(0 \leq t \leq mn-2\), (c) \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches for \(0 \leq t \leq mn-2\), and (d) \(L(u_{i_t}) \leq d/2\) for all \(0 \leq t \leq mn-1\). Hence the conditions (a)-(d) in Theorem 3.3 are satisfied. We now show that the condition (e) of Theorem 3.3 holds.
The above defined ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T^1 \Box K_n)\) satisfies (13).
Let \(w_a=(u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b})\;(0 \leq a < b \leq mn-1)\) be two vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch when viewed as vertices of \(T^1\). Denote the right-hand side of (13) by \(P_{a,b}\). In this case, note that \(d_0 \geq 3\), \(\varepsilon= 1\) and \(L(u_{t}) \leq d/2\) for all \(0 \leq t \leq mn-1\). Observe that for \(w_a = (u_{i_a},v_{j_a)}\) and \(w_b = (u_{i_b},v_{j_b})\) such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T^2\), there are two possibilities: (1) \(i_a \neq i_b\) (2) \(i_a = i_b\). In case (1), we have \(b-a \geq \alpha d_0\), where \(\alpha \geq \phi(u_{i_a},u_{i_b})\). Hence, \(P_{a,b} = \left((b-a-1)/2\right)(d+1)-\sum\limits_{t=a+1}^{b-1}L(u_{i_{t}}) \geq \left((b-a-1)/2\right)(d+1)\)\(-\sum\limits_{t=a+1}^{b-1}(d/2) = \left((b-a-1)/2\right) = \alpha (d_0-1)/2 \geq \phi(u_{i_a},u_{i_b})\). In case (2), note that \(b-a \geq m \geq d+1\). Hence, \(P_{a,b} = \left((b-a-1)/2\right)(d+1)-\sum\limits_{t=a+1}^{b-1}L(u_{i_{t}}) \geq \left((b-a-1)/2\right)(d+1)- \sum\limits_{t=a+1}^{b-1}(d/2) = \left((b-a-1)/2\right) \)\(= d/2 \geq \phi(u_{i_a},u_{i_b})\).
Case 2. \(|W(T)|=2\)
Again we consider the following two subcases to define an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T^2 \Box K_n)\).
Subcase 1. \(|V(T)| \leq |V(K_n)|\).
In this case, for \(0 \leq t \leq mn-1\), define \(w_t := (u_i,v_j)\), where \(i \in \{0,1,\ldots,m-1\}, j \in \{0,1,\ldots,n-1\}\) and \[t := \left\{ \begin{array}{ll} m(j-i)+i, & \mbox{if $j\geq i$}, \\[0.2cm] m(n+j-i)+i, & \mbox{if $j<i$}. \end{array} \right.\]
Subcase 2. \(|V(T)| > |V(K_n)|\).
In this case, define an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(T^2 \Box K_n)\) as follows: For \(x\mathop{\mathrm{lcm}}(m,n) \leq t \leq (x+1)\mathop{\mathrm{lcm}}(m,n)-1\), where \(0 \leq x \leq \gcd(m,n)-1\), set \[w_t := \left\{ \begin{array}{ll} (u_i,v_{j+x}), & \mbox{if $t \equiv i$ (mod $m$), $t \equiv j$ (mod $n$) and $0\leq j\leq n-(x+1)$}, \\[0.2cm] (u_i,v_{j+x-n}), & \mbox{if $t \equiv i$ (mod $m$), $t \equiv j$ (mod $n$) and $n-x\leq j\leq n-1$}, \\[0.2cm] \end{array} \right.\]
Then, for above defined ordering, it is clear that (a) \(L(u_{i_0}) = L(u_{i_{mn-1}}) = L(u_0) = 0\), (b) \(v_{j_t}\) and \(v_{j_{t+1}}\) are distinct for \(0 \leq t \leq mn-2\), (c) \(u_{i_t}\) and \(u_{i_{t+1}}\) are in different branches for \(0 \leq t \leq mn-2\), and (d) \(L(u_{i_t}) \leq (d-1)/2\) for all \(0 \leq t \leq mn-1\). Hence the conditions (a)-(d) of Theorem 3.3 are satisfied. Now we prove that the condition (e) of Theorem 3.3 holds.
Let \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b})\;(0 \leq a < b \leq mn-1)\) be two vertices such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch when viewed as vertices of \(T^2\). Denote the right-hand side of (13) by \(P_{a,b}\). In this case, note that \(d_0 \geq 3\), \(\varepsilon= 0\) and \(L(u_t) \leq (d-1)/2\) for all \(0 \leq t \leq mn-1\). Observe that for \(w_a = (u_{i_a},v_{j_a})\) and \(w_b = (u_{i_b},v_{j_b})\) such that \(u_{i_a}\) and \(u_{i_b}\) are in the same branch of \(T^2\), there are two possibilities: (1) \(i_a \neq i_b\), (2) \(i_a = i_b\). In case (1), we have \(b-a \geq \alpha (d_0-1)\), where \(\alpha \geq \phi(u_{i_a},u_{i_b})\). Hence, \(P_{a,b} = \left((b-a-1)/2\right)d-\sum\limits_{t=a+1}^{b-1}L(u_{i_t})-1/2 \geq \left((b-a-1)/2\right)d-\sum\limits_{t=a+1}^{b-1}((d-1)/2)-1/2 \)\(= (b-a-2)/2 = \alpha(d_0-1)/2 \geq \phi(u_{i_a},u_{i_b})\). In case (2), note that \(b-a \geq m \geq d+1\). Hence, \(P_{a,b} = \left((b-a-1)/2\right)d\)\(-\sum\limits_{t=a+1}^{b-1}L(u_{i_t})-1/2 \geq \left((b-a-1)/2\right)d-\sum\limits_{t=a+1}^{b-1}((d-1)/2)-1/2 = (b-a-2)/2 = \alpha(d-1)/2 \geq \phi(u_{i_a},u_{i_b})\). ◻
| \((u_i,v_j)\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | \(v_6\) |
|---|---|---|---|---|---|---|---|
| \(u_0\) | \(w_{0} \rightarrow 0\) | \(w_{7} \rightarrow 9\) | \(w_{14} \rightarrow 18\) | \(w_{21} \rightarrow 27\) | \(w_{28} \rightarrow 36\) | \(w_{35} \rightarrow 45\) | \(w_{48} \rightarrow 60\) |
| \(u_1\) | \(w_{42} \rightarrow 53\) | \(w_{1} \rightarrow 2\) | \(w_{8} \rightarrow 11\) | \(w_{15} \rightarrow 20\) | \(w_{22} \rightarrow 29\) | \(w_{29} \rightarrow 38\) | \(w_{36} \rightarrow 47\) |
| \(u_2\) | \(w_{37} \rightarrow 48\) | \(w_{43} \rightarrow 54\) | \(w_{2} \rightarrow 3\) | \(w_{9} \rightarrow 12\) | \(w_{16} \rightarrow 21\) | \(w_{23} \rightarrow 30\) | \(w_{30} \rightarrow 39\) |
| \(u_3\) | \(w_{31} \rightarrow 40\) | \(w_{38} \rightarrow 49\) | \(w_{44} \rightarrow 55\) | \(w_{3} \rightarrow 4\) | \(w_{10} \rightarrow 13\) | \(w_{17} \rightarrow 22\) | \(w_{24} \rightarrow 31\) |
| \(u_4\) | \(w_{25} \rightarrow 32\) | \(w_{32} \rightarrow 41\) | \(w_{39} \rightarrow 50\) | \(w_{45} \rightarrow 56\) | \(w_{4} \rightarrow 5\) | \(w_{11} \rightarrow 14\) | \(w_{18} \rightarrow 23\) |
| \(u_5\) | \(w_{19} \rightarrow 24\) | \(w_{26} \rightarrow 33\) | \(w_{33} \rightarrow 42\) | \(w_{40} \rightarrow 51\) | \(w_{46} \rightarrow 57\) | \(w_{5} \rightarrow 6\) | \(w_{12} \rightarrow 15\) |
| \(u_6\) | \(w_{13} \rightarrow 16\) | \(w_{20} \rightarrow 25\) | \(w_{27} \rightarrow 34\) | \(w_{34} \rightarrow 43\) | \(w_{41} \rightarrow 52\) | \(w_{47} \rightarrow 58\) | \(w_{6} \rightarrow 7\) |
| \((u_i,v_j)\) | \(v_0\) | \(v_1\) | \(v_2\) | \(v_3\) | \(v_4\) | \(v_5\) | \(v_6\) |
|---|---|---|---|---|---|---|---|
| \(u_0\) | \(w_{0} \rightarrow 0\) | \(w_{36} \rightarrow 48\) | \(w_{72} \rightarrow 96\) | \(w_{24} \rightarrow 32\) | \(w_{60} \rightarrow 80\) | \(w_{12} \rightarrow 16\) | \(w_{48} \rightarrow 64\) |
| \(u_1\) | \(w_{49} \rightarrow 66\) | \(w_{1} \rightarrow 2\) | \(w_{37} \rightarrow 50\) | \(w_{73} \rightarrow 98\) | \(w_{25} \rightarrow 34\) | \(w_{61} \rightarrow 82\) | \(w_{13} \rightarrow 18\) |
| \(u_2\) | \(w_{14} \rightarrow 19\) | \(w_{50} \rightarrow 67\) | \(w_{2} \rightarrow 3\) | \(w_{38} \rightarrow 51\) | \(w_{74} \rightarrow 99\) | \(w_{26} \rightarrow 35\) | \(w_{62} \rightarrow 83\) |
| \(u_3\) | \(w_{63} \rightarrow 84\) | \(w_{15} \rightarrow 20\) | \(w_{51} \rightarrow 68\) | \(w_{3} \rightarrow 4\) | \(w_{39} \rightarrow 52\) | \(w_{75} \rightarrow 100\) | \(w_{27} \rightarrow 36\) |
| \(u_4\) | \(w_{28} \rightarrow 37\) | \(w_{64} \rightarrow 85\) | \(w_{16} \rightarrow 21\) | \(w_{52} \rightarrow 69\) | \(w_{4} \rightarrow 5\) | \(w_{40} \rightarrow 53\) | \(w_{76} \rightarrow 101\) |
| \(u_5\) | \(w_{77} \rightarrow 102\) | \(w_{29} \rightarrow 38\) | \(w_{65} \rightarrow 86\) | \(w_{17} \rightarrow 22\) | \(w_{53} \rightarrow 70\) | \(w_{5} \rightarrow 6\) | \(w_{41} \rightarrow 54\) |
| \(u_6\) | \(w_{42} \rightarrow 55\) | \(w_{78} \rightarrow 103\) | \(w_{30} \rightarrow 39\) | \(w_{66} \rightarrow 87\) | \(w_{18} \rightarrow 23\) | \(w_{54} \rightarrow 71\) | \(w_{6} \rightarrow 7\) |
| \(u_7\) | \(w_{7} \rightarrow 8\) | \(w_{43} \rightarrow 56\) | \(w_{79} \rightarrow 104\) | \(w_{31} \rightarrow 40\) | \(w_{67} \rightarrow 88\) | \(w_{19} \rightarrow 24\) | \(w_{55} \rightarrow 72\) |
| \(u_8\) | \(w_{56} \rightarrow 73\) | \(w_{8} \rightarrow 9\) | \(w_{44} \rightarrow 57\) | \(w_{80} \rightarrow 105\) | \(w_{32} \rightarrow 41\) | \(w_{68} \rightarrow 89\) | \(w_{20} \rightarrow 25\) |
| \(u_9\) | \(w_{21} \rightarrow 26\) | \(w_{57} \rightarrow 74\) | \(w_{9} \rightarrow 10\) | \(w_{45} \rightarrow 58\) | \(w_{81} \rightarrow 106\) | \(w_{33} \rightarrow 42\) | \(w_{69} \rightarrow 90\) |
| \(u_{10}\) | \(w_{70} \rightarrow 91\) | \(w_{22} \rightarrow 27\) | \(w_{58} \rightarrow 75\) | \(w_{10} \rightarrow 11\) | \(w_{46} \rightarrow 59\) | \(w_{82} \rightarrow 107\) | \(w_{34} \rightarrow 43\) |
| \(u_{11}\) | \(w_{35} \rightarrow 45\) | \(w_{71} \rightarrow 93\) | \(w_{23} \rightarrow 29\) | \(w_{59} \rightarrow 77\) | \(w_{11} \rightarrow 13\) | \(w_{47} \rightarrow 61\) | \(w_{83} \rightarrow 109\) |
In [11], Kim et al. determined the radio number of a path \(P_m (m \geq 4)\) and the complete graph \(K_n (n \geq 3)\) as follows: \[\label{rn:PmKn} {\rm rn}(P_m \Box K_n) = \begin{cases} \frac{m^2n-2m+2}{2}, & \mbox{if $m$ is even}, \\ \frac{m^2n-2m+n+2}{2}, & \mbox{if $m$ is odd}. \end{cases} \tag{16}\] This result can be proved using our results. The outline of the proof is as follows: Since a path \(P_m\) is a tree, we use Theorems 3.1 and 3.2 to prove the result. Note that the diameter \(d\) of \(P_m\) is \(m-1\). We consider the following two cases.
Case 1. \(m\) is even. In this case, the total level of a path \(P_m\) is given by \(L(P_m) = m(m-2)/2\). Substituting this into (6), we obtain \({\rm rn}(P_m \Box K_n) \geq (m^2n-2m+2)/2\). Now observe that the ordering of \(V(P_m \Box K_n)\) given in [11] satisfies the conditions (a)-(c) in Theorem 3.2 and hence we obtain that the first line in (16) holds.
Case 2. \(m\) is odd. In this case, the total level of a path \(P_m\) is given by \(L(P_m) = (m^2-1)/2\). Substituting this into (6), we obtain \({\rm rn}(P_m \Box K_n) \geq (m^2n-2m+n)/2\). Now assume that \({\rm rn}(P_m \Box K_n) = (m^2n-2m+n)/2\). Then by Theorem 3.2, there exists an ordering \(w_0,w_1,\ldots,w_{mn-1}\) of \(V(P_m \Box K_n)\) such that the conditions (a)-(c) in Theorem 3.2 hold. Since \(L(u_{i_0}) = L(u_{i_{mn-1}})\) by (a), observe that there exists a vertex \(w_k = (u_{i_k},v_{j_k})\) such that \(L(u_{i_k}) = (m-1)/2\) and \(L(u_{i_{k-1}}) \neq 0, L(u_{i_{k+1}}) \neq 0\). Note that \(d(u_{i_{k-1}},u_{i_{k+1}}) = L(u_{i_{k-1}})+L(u_{i_{k+1}})-2\phi(u_{i_{k-1}},u_{i_{k+1}})\) with \(\phi(u_{i_{k-1}},u_{i_{k+1}}) \geq 1\). Denote the right-hand side of (9) by \(S_{a,b}\) and consider \(u_{i_{k-1}}\) and \(u_{i_{k+1}}\) in (9). Then we obtain \(S_{k-1,k+1} = L(u_{i_{k-1}})+2L(u_{i_k})\)\(+L(u_{i_{k+1}})-(d+1) = L(u_{i_k})+2((d+1)/2)+L(u_{i_{k+1}})-(d+1) = L(u_{i_{k-1}})+L(u_{i_{k+1}}) > L(u_{i_{k-1}})+L(u_{i_{k+1}})\)\(-2\phi(u_{i_{k-1}},u_{i_{k+1}}) = d(u_{i_{k-1}},u_{i_{k+1}})\), which is a contradiction. Hence, \({\rm rn}(P_m \Box K_n) \geq (m^2n-2m+n+2)/2\). Now observe that the ordering of \(V(P_m \Box K_n)\) given in [11] satisfies the conditions (a)-(c) in Theorem 3.2. Hence we obtain that the second line in (16) holds, and this completes the proof.
The authors are grateful to the two anonymous referees for their careful reading of the manuscript and helpful comments. The research of the second author is supported by Research Promotion under Technical Education – STEM research project grant (Project ID: 202122MATH01) of the Government of Gujarat.
The authors have no relevant financial or non-financial interests to disclose.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.