# Radio number for the Cartesian product of a tree and a complete graph

Payal Vasoya<EMAIL_ADDRESS>(Payal Vasoya) Gujarat Technogical
University, Ahmedabad - 382 424, Gujarat, India  Devsi Bantva
<EMAIL_ADDRESS>(Devsi Bantva)Corresponding author. Lukhdhirji
Engineering College, Morvi 363 642, Gujarat, India

###### Abstract

A radio labelling of a graph $G$ is a mapping
$f:V(G)\rightarrow\\{0,1,2,\ldots\\}$ such that $|f(u)-f(v)|\geq{\rm
diam}(G)+1-d(u,v)$ for every pair of distinct vertices $u,v$ of $G$, where
${\rm diam}(G)$ is the diameter of $G$ and $d(u,v)$ is the distance between
$u$ and $v$ in $G$. The radio number ${\rm rn}(G)$ of $G$ is the smallest
integer $k$ such that $G$ admits a radio labelling $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 to achieve the lower bound. We also give three
sufficient conditions to achieve the lower bound. We determine the radio
number for the Cartesian product of a level-wise regular trees and a complete
graph which attains the lower bound. The radio number for the Cartesian
product of a path and a complete graph derived in [11] can be obtained using
our results in a short way.

_Keywords_ : Radio labelling, radio number, Cartesian product, tree, Complete
graph.

_AMS Subject Classification (2010)_ : 05C78, 05C15, 05C12.

##  1 Introduction

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; 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 [6, 7], 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 - the diameter of a graph.

######  Definition 1.1.

A _radio labelling_ of a graph $G$ is a mapping
$f:V(G)\rightarrow\\{0,1,2,\ldots\\}$ such that the following hold for every
pair of distinct vertices $u,v$ of $G$,

$|f(u)-f(v)|\geq{\rm diam}(G)+1-d(u,v).$ (1)

The integer $f(u)$ is called the _label_ of $u$ under $f$, and the _span_ of
$f$ is defined as ${\rm span}(f)=\max\\{|f(u)-f(v)|:u,v\in V(G)\\}$. The
_radio number_ of $G$ is defined as

${\rm rn}(G)=\min_{f}{\rm span}(f)$

with minimum taken over all radio labellings $f$ of $G$. A radio labelling $f$
of $G$ is called _optimal_ if ${\rm span}(f)={\rm rn}(G)$.

Observe that a 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 then 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

$\vec{V}_{f}:a_{0},a_{1},\ldots,a_{m-1}$ (2)

of the vertices of $G$ such that

$0=f(a_{0})<f(a_{1})<\ldots<f(a_{m-1})={\rm span}(f).$ (3)

A linear order $a_{0},a_{1},\ldots,a_{m-1}$ of $V(T)$ is called optimal linear
order if it induced by some optimal radio labelling $f$ of $T$.

The determining radio number of graphs is a tough and challenging task. The
radio number is known only for very few graphs and the 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\geq 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 to achieve the lower bound. The authors gave three other sufficient
conditions to achieve 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) to achieve 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 for the Cartesian
product of a path and a complete graph given in [11] can be obtained using our
results in a short way.

##  2 Preliminaries

We follow [18] 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 every 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_{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)$.

######  Lemma 2.1.

[13] If $r$ is a weight center of a tree $T$. Then each component of $T-r$
contains at most $|V(T)|/2$ vertices.

######  Lemma 2.2.

[13] Every tree $T$ has one or two weight centers, and $T$ has two weight
centers, say, $W(T)=\\{r,r^{\prime}\\}$ if and only if $rr^{\prime}$ is an
edge of $T$ and $T-rr^{\prime}$ consists of two equal sized components.

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 consists only one weight center and in
_opposite branches_ if the path joining them consists 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^{\prime}\\}$, then $T$ is rooted at $r$
and $r^{\prime}$ in the sense that both $r$ and $r^{\prime}$ 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_{u\in V(T)}L(u)$

the _total level_ of $T$. For any $u,v\in V(T)$, define

$\phi(u,v)=\mbox{max}\\{L(x):x\mbox{ is a common ancestor of $u$ and $v$}\\},$
$\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}$

######  Lemma 2.3 ([3, Lemma 2.1]).

Let $T$ be a tree with diameter $d\geq 2$. Then for any $u,v\in V(T)$ the
following hold:

  1. (a)

$\phi(u,v)\geq 0$;

  2. (b)

$\phi(u,v)=0$ if and only if $u$ and $v$ are in different or opposite
branches;

  3. (c)

$\delta(u,v)=1$ if and only if $T$ has two weight centers and $u$ and $v$ are
in opposite branches;

  4. (d)

the distance $d(u,v)$ in $T$ between $u$ and $v$ can be expressed as

$d(u,v)=L(u)+L(v)-2\phi(u,v)+\delta(u,v).$ (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)$ and
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})$.

######  Observation 2.4.

For a tree $T$ of order $m\,(m\geq 2)$ and a complete graph $K_{n}$,

  1. (a)

$|V(T\Box K_{n})|=mn$,

  2. (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 note that 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$ appear
$n$ times and each vertex $v_{j},\;j=0,1,\ldots,n-1$ appear $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

$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}})$
(5)

##  3 A tight lower bound for ${\rm rn}(T\Box K_{n})$

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 to achieve the
lower bound.

######  Theorem 3.1.

Let $T$ be a tree of order $m$ and diameter $d\geq 2$. Denote
$\varepsilon=\varepsilon(T)$. Then

${\rm rn}(T\Box K_{n})\geq(mn-1)(d+\varepsilon)-2nL(T).$ (6)

###### Proof.

It is enough to prove that any radio labelling of $T\Box K_{n}$ has no span
less than that the right-hand side of (6). Suppose $f$ be 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})<\ldots<f(w_{mn-1})$. Denote ${\rm diam}(T\Box
K_{n})=d^{\prime}$. By the definition of radio labelling,
$f(w_{t+1})-f(w_{t})\geq d^{\prime}+1-d(w_{t},w_{t+1})$ for $0\leq t\leq
mn-2$. Since $d^{\prime}=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

${\rm span}(f)=f(w_{mn-1})\geq(mn-1)(d+2)-\sum_{t=0}^{mn-2}d(w_{t},w_{t+1}).$
(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

$\displaystyle\sum_{t=0}^{mn-2}d(w_{t},w_{t+1})$ $\displaystyle=$
$\displaystyle\sum_{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}})]$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{mn-2}[L(u_{i_{t}})+L(u_{i_{t+1}})+d(v_{j_{t}},v_{j_{t+1}})]$
$\displaystyle\leq$ $\displaystyle
2n\sum_{i=0}^{m-1}L(u_{i})+(mn-1)-L(u_{i_{0}})-L(u_{i_{mn-1}})$
$\displaystyle\leq$ $\displaystyle 2nL(T)+mn-1.$

Substituting this in (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

$\displaystyle\sum_{t=0}^{mn-2}d(w_{t},w_{t+1})$ $\displaystyle=$
$\displaystyle\sum_{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}})$
$\displaystyle\hskip 199.16928pt+d(v_{j_{t}},v_{j_{t+1}})]$
$\displaystyle\leq$
$\displaystyle\sum_{t=0}^{mn-2}[L(u_{i_{t}})+L(u_{i_{t+1}})+1+d(v_{j_{t}},v_{j_{t+1}})]$
$\displaystyle\leq$ $\displaystyle
2n\sum_{i=0}^{m-1}L(u_{i})+(mn-1)+(mn-1)-L(u_{i_{0}})-L(u_{i_{mn-1}})$
$\displaystyle\leq$ $\displaystyle 2nL(T)+2(mn-1).$

Substituting this in (7), we have ${\rm span}(f)\geq(mn-1)d-2nL(T)$. ∎

######  Theorem 3.2.

Let $T$ be a tree of order $m$ and diameter $d\geq 2$. Denote
$\varepsilon=\varepsilon(T)$. Then

${\rm rn}(T\Box K_{n})=(mn-1)(d+\varepsilon-2nL(T)$ (8)

if and only if there exist an ordering $w_{0},w_{1},\ldots,w_{mn-1}$ of
$V(T\Box K_{n})$ such that the following hold:

  1. (a)

$L(u_{i_{0}})=L(u_{i_{mn-1}})=0$,

  2. (b)

$v_{j_{t}}$ and $v_{j_{t+1}}$ are distinct for all $0\leq t\leq mn-2$,

  3. (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

$d(u_{i_{a}},u_{i_{b}})\geq\sum_{t=a}^{b-1}[L(u_{i_{t}})+L(u_{i_{t+1}})-(d+\varepsilon)]+(d+1).$
(9)

Moreover, under these conditions (a)-(c), the mapping $f$ defined by

$f(w_{0})=0$ (10)
$f(w_{t+1})=f(w_{t})+d+\varepsilon-L(u_{i_{t}})-L(u_{i_{t+1}}),0\leq t\leq
mn-2$ (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 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^{\prime}+\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^{\prime}={\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_{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^{\prime}+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
in the above equation, we obtain

$d(u_{i_{a}},u_{i_{b}})\geq\sum_{t=a}^{b-1}[L(u_{i_{t}})+L(u_{i_{t+1}})-(d+\varepsilon)]+(d+1).$

Sufficiency: Suppose there exist 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^{\prime}$. Let $w_{a}$ and $w_{b}\;(0\leq
a<b\leq mn-1)$ be two arbitrary vertices.

$\displaystyle f(w_{b})-f(w_{a})$ $\displaystyle=$
$\displaystyle\sum_{t=a}^{b-1}(f(w_{t+1})-f(w_{t}))$ $\displaystyle=$
$\displaystyle\sum_{t=a}^{b-1}(d+\varepsilon-L(u_{i_{t}})-L(u_{i_{t+1}}))$
$\displaystyle=$ $\displaystyle d+1-d(u_{i_{a}},u_{i_{b}})$ $\displaystyle=$
$\displaystyle d+2-(d(u_{i_{a}},u_{i_{b}})+1)$ $\displaystyle=$ $\displaystyle
d^{\prime}+1-d(w_{a},w_{b}).$

The span of $f$ is

$\displaystyle{\rm span}(f)$ $\displaystyle=$ $\displaystyle
f(w_{mn-1})-f(w_{0})$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{mn-2}(f(w_{t+1})-f(w_{t}))$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{mn-2}(d+\varepsilon-L(u_{i_{t}})-L(u_{i_{t+1}}))$
$\displaystyle=$
$\displaystyle(mn-1)(d+\varepsilon)-2\sum_{t=0}^{mn-2}L(u_{i_{t}})+L(u_{i_{0}})+L(u_{i_{mn-1}})$
$\displaystyle=$ $\displaystyle(mn-1)(d+\varepsilon)-2nL(T).$

∎

######  Theorem 3.3.

Let $T$ be a tree of order $m$ and diameter $d\geq 2$. Denote
$\varepsilon=\varepsilon(T)$. Then

${\rm rn}(T\Box K_{n})=(mn-1)(d+\varepsilon)-2nL(T)$ (12)

if and only if there exist an ordering $w_{0},w_{1},\ldots,w_{mn-1}$ with
$w_{t}=(u_{i_{t}},v_{j_{t}}),0\leq t\leq mn-1$ of $V(T\Box K_{n})$ such that
the following all hold:

  1. (a)

$L(u_{i_{0}})=L(u_{i_{mn-1}})=0$,

  2. (b)

$v_{j_{t}}$ and $v_{j_{t+1}}$ are distinct for $0\leq t\leq mn-2$,

  3. (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$,

  4. (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$;

  5. (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$ then $u_{i_{a}}$ and $u_{i_{b}}$ satisfies

$\phi(u_{i_{a}},u_{i_{b}})\leq\left(\frac{b-a-1}{2}\right)(d+\varepsilon)-\sum_{t=a+1}^{b-1}L(u_{i_{t}})-\left(\frac{1-\varepsilon}{2}\right).$
(13)

###### Proof.

Necessity: Suppose (12) holds. Then there exist 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) satisfies. 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)
satisfies. 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$, consider
$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) satisfies. 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), the (13) can be obtain
easily from (9).

Sufficiency: Suppose there exist an ordering $(w_{0},w_{1},\ldots,w_{mn-1})$
of $V(T\Box K_{n})$ such that conditions (a)-(e) holds. To prove (12) holds,
we show that an ordering $w_{0},w_{1},\ldots,w_{mn-1}$ satisfies the condition
(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_{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_{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 obtain easily using (13)
which complete the proof. ∎

######  Theorem 3.4.

Let $T$ be a tree of order $m$ and diameter $d\geq 2$. Denote
$\varepsilon=\varepsilon(T)$. Then

${\rm rn}(T\Box K_{n})=(mn-1)(d+\varepsilon)-2nL(T)$ (14)

if there exist an ordering $w_{0},w_{1},\ldots,w_{mn-1}$ of $V(T\Box K_{n})$
such that

  1. (a)

$L(u_{i_{0}})=L(u_{i_{mn-1}})=0$,

  2. (b)

$v_{j_{t}}$ and $v_{j_{t+1}}$ are distinct for all $0\leq t\leq mn-2$,

  3. (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:

  1. (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$,

  2. (e)

$d(u_{i_{t}},u_{i_{t+1}})\leq(d+1+\varepsilon)/2$ for all $0\leq t\leq mn-2$,

  3. (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 the (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 satisfies. 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) holds. 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 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) holds. 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) holds. 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) holds. 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, 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) holds. 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) holds. 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}})$. ∎

##  4 Radio number for the Cartesian product of level-wise regular tree and
complete graph

In this section, using the results of Section 3, we determine the radio number
for 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^{\prime}$ depending on ${\rm diam}(T)$ is even or odd.
We view a tree $T$ rooted at $r$ or at both $r,r^{\prime}$ 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^{\prime}\\}$ 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 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 star graphs. Note that
a star $K_{1,q}$, double star $D_{q}$ and a banana tree $B_{q,k}$ are level-
wise regular trees $T^{1}_{q}$, $T^{2}_{q+1}$ and $T^{1}_{q,2,k}$,
respectively.

######  Theorem 4.1.

Let $h\geq 1$ and $d_{i},n\geq 3$ for $0\leq i\leq h-1$ be any integers.
Denote $\varepsilon=\varepsilon(T^{z})$. Then ${\rm rn}(T^{z}\Box K_{n})$

$=\left\\{\begin{array}[]{ll}\left[\left(\displaystyle\sum_{i=1}^{h-1}(2h-2i-1)\left(\prod_{1\leq
j\leq i}(d_{j}-1)\right)\right)+2h-1\right]nd_{0}+(2h+1)(n-1),&\mbox{if
$z=1$},\\\\[17.07182pt]
\left[\left(\displaystyle\sum_{i=0}^{h-1}(2h-2i-1)\left(\prod_{0\leq j\leq
i}(d_{j}-1)\right)\right)+2h+1\right]2n-2h-1,&\mbox{if
$z=2$}.\end{array}\right.$ (15)

###### 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_{i=1}^{h-1}\left(\displaystyle\prod_{1\leq
j\leq i}(d_{j}-1)\right),&\mbox{if $z=1$},\\\
2+2\displaystyle\sum_{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_{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_{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 in (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
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}$ got 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_{2}d_{0}+\ldots+i_{l}d_{0}(d_{1}-1)\ldots(d_{l}-1)+\displaystyle\sum_{l+1\leq
t\leq h}d_{0}(d_{1}-1)\ldots(d_{t}-1)$.

Case-2: $z=2$.

In this case, let $r$ and $r^{\prime}$ be two centers of $T^{2}$. Denote
$d_{0}-1$ children of $r$ and $r^{\prime}$ by $r_{0},r_{1},\ldots,r_{d_{0}-2}$
and $r^{\prime}_{0},r^{\prime}_{1},\ldots,r^{\prime}_{d_{0}-2}$, respectively.
For $0\leq i\leq d_{0}-2$, denote $d_{1}-1$ children of $r_{i}$ and
$r^{\prime}_{i}$ by $r_{i,0},r_{i,1},\ldots,r_{i,d_{1}-1}$ and
$r^{\prime}_{i,0},r^{\prime}_{i,1},\ldots,r^{\prime}_{i,d_{1}-1}$,
respectively. Inductively, denote the $d_{l}-1$ children of
$r_{i_{1},i_{2},\ldots,i_{l}}$ and $r^{\prime}_{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^{\prime}_{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}$
got indexed. Rename $x_{j}:=r_{i_{1},i_{2},\ldots,i_{l}}\mbox{ and
}x^{\prime}_{j}:=r^{\prime}_{i_{1},i_{2},\ldots,i_{l}}$, where
$j=1+i_{1}+i_{2}(d_{0}-1)+\ldots+i_{l}(d_{0}-1)(d_{1}-1)\ldots(d_{l}-1)+\displaystyle\sum_{l+1\leq
t\leq h}(d_{0}-1)(d_{1}-1)\ldots(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^{\prime}$
and for $1\leq t\leq m-2$, set

$u_{t}:=\begin{cases}x_{t/2},&\mbox{if $t\equiv 0$ (mod $2$)},\\\
x^{\prime}_{(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$},\\\\[5.69046pt] m(n+j-i)+i&\mbox{if $j<i$ and $i-j\neq
1$},\\\\[5.69046pt] m(n+j-i)+i-1&\mbox{if $j<i$ and $i-j=1$},\\\\[5.69046pt]
mn-1&\mbox{if $j-i=n-1$}.\\\\[5.69046pt] \end{array}\right.$

Subcase 2: $|V(T^{1})|>|V(K_{n})|$.

In this case, for $x\operatorname{lcm}(m,n)\leq
t\leq(x+1)\operatorname{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)$},\\\\[5.69046pt]
(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$},\\\\[5.69046pt] \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$},\\\\[5.69046pt] \alpha_{t+1},&\mbox{if $mn-m\leq t\leq
mn-2$},\\\\[5.69046pt] \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) of Theorem 3.3 are
satisfies. We now show that the condition (e) of Theorem 3.3 holds as follows.

Claim-1: 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
$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}}$ both are in the same branch of $T^{2}$ then there
are two possibilities: (1) $i_{a}\neq i_{b}$ (2) $i_{a}=i_{b}$. In case of
(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_{t=a+1}^{b-1}L(u_{i_{t}})\geq\left((b-a-1)/2\right)(d+1)-\sum_{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 of (2), note that $b-a\geq m\geq d+1$. Hence,
$P_{a,b}=\left((b-a-1)/2\right)(d+1)-\sum_{t=a+1}^{b-1}L(u_{i_{t}})\geq\left((b-a-1)/2\right)(d+1)-\sum_{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$},\\\\[5.69046pt]
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\operatorname{lcm}(m,n)\leq
t\leq(x+1)\operatorname{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)$},\\\\[5.69046pt]
(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$},\\\\[5.69046pt] \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 as
follows.

Claim-2: The above defined ordering $w_{0},w_{1},\ldots,w_{mn-1}$ of
$V(T^{2}\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^{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
$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}}$ both are in the same branch of $T^{2}$ then there
are two possibilities: (1) $i_{a}\neq i_{b}$, (2) $i_{a}=i_{b}$. In case of
(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_{t=a+1}^{b-1}L(u_{i_{t}})-1/2\geq\left((b-a-1)/2\right)d-\sum_{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 of (2), note that $b-a\geq m\geq d+1$. Hence,
$P_{a,b}=\left((b-a-1)/2\right)d-\sum_{t=a+1}^{b-1}L(u_{i_{t}})-1/2\geq\left((b-a-1)/2\right)d-\sum_{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}})$.
∎

######  Corollary 4.2.

Let $q\geq 3$ and $n\geq 4$ be any integers. Then

${\rm rn}(K_{1,q}\Box K_{n})=(q+3)n-3.$

######  Corollary 4.3.

Let $q\geq 2$ and $n\geq 4$ be any integers. Then

${\rm rn}(D_{q}\Box K_{n})=2n(q+3)-3.$

######  Corollary 4.4.

Let $k,n\geq 4$ and $q\geq 5$ be any integers. Then

${\rm rn}(B_{q,k}\Box K_{n})=qn(k+6)+7(n-1).$

######  Example 4.1.

In Table 1, a vertex ordering $O(V(K_{1,6}\Box
K_{7})):=w_{0},w_{1},\ldots,w_{48}$ and an optimal radio labelling of
$K_{1,6}\Box K_{7}$ are shown.

Table 1: ${\rm rn}(K_{1,6}\Box K_{7})=60$. $(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 12$ | $w_{47}\rightarrow 58$ | $w_{6}\rightarrow 7$

######  Example 4.2.

In Table 2, a vertex ordering $O(V(D_{5}\Box
K_{7})):=w_{0},w_{1},\ldots,w_{83}$ and an optimal radio labelling of
$D_{5}\Box K_{7}$ are shown.

Table 2: ${\rm rn}(D_{5}\Box K_{7})=$109. $(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$

## Concluding Remarks

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:

${\rm rn}(P_{m}\Box K_{n})=\begin{cases}\frac{m^{2}n-2m+2}{2},&\mbox{if $m$ is
even},\\\ \frac{m^{2}n-2m+n+2}{2},&\mbox{if $m$ is odd}.\end{cases}$ (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 Theorem 3.1 and 3.2 to prove
the result. Note that the diameter $d$ of a path $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 in (6), we obtain ${\rm
rn}(P_{m}\Box K_{n})\geq(m^{2}n-2m+2)/2$. Now observe that the ordering of
$V(P_{m}\Box K_{n})$ given in [11] satisfies the conditions (a)-(c) of 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 in (6), we obtain ${\rm
rn}(P_{m}\Box K_{n})\geq(m^{2}n-2m+n)/2$. Now if possible then assume that
${\rm rn}(P_{m}\Box K_{n})=(m^{2}n-2m+n)/2$ then by Theorem 3.2, there exist
an ordering $w_{0},w_{1},\ldots,w_{mn-1}$ of $V(P_{m}\Box K_{n})$ such that
the conditions (a)-(c) of Theorem 3.2 hold. Since
$L(u_{i_{0}})=L(u_{i_{mn-1}})$ by (a), observe that there exist 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^{2}n-2m+n+2)/2$. Now observe that the ordering of $V(P_{m}\Box
K_{n})$ given in [11] satisfies the conditions (a)-(c) of Theorem 3.2 and
hence we obtain that the second line in (16) holds which completes the proof.

## References

  * [1] D. Bantva, Further results on the radio of trees, _Electron. Notes Discrete Math._ 63 (2017), 85–91.
  * [2] D. Bantva and D. Liu, Optimal radio labellings of block graphs and line graphs of trees, _Theoretical Computer Science_ 891 (2021), 90–104.
  * [3] D. Bantva, S. Vaidya and S. Zhou, Radio number of trees, _Discrete Appl. Math._ 217 (2017), 110–122.
  * [4] K. F. Benson, M. Porter, M. Kanwal, The radio numbers of all graphs of order $n$ and diameter $n-2$, _Le Matematiche_ , 68 (2013), 167–190.
  * [5] T. Calamoneri, The $L(h,k)$-labelling problem: An updated survey and annotated bibliography, _The Computer Journal_ , 54(8) (2011), 1344–1371.
  * [6] G. Chartrand, D. Erwin, F. Harary and P. Zhang, Radio labellings of graphs, _Bull. Inst. Combin. Appl._ , 33 (2001), 77–85.
  * [7] G. Chartrand, D. Erwin and P. Zhang, A graph labelling suggested by FM channel restrictions, _Bull. Inst. Combin. Appl._ , 43 (2005) 43–57.
  * [8] J. R. Griggs and R. K. Yeh, Labelling graphs with condition at distance 2, _SIAM J. Discrete Math._ , 5(4) (1992), 586–595.
  * [9] V. Halász and Z. Tuza, Distance-constrained labelling of complete trees, _Discrete Math._ , 338 (2015) 1398–1406.
  * [10] W. K. Hale, Frequency assignment: Theory and applications, _Proc. IEEE_ , 68(12) (1980), 1497–1514.
  * [11] 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.
  * [12] X. Li, V. Mak and S. Zhou, Optimal radio labellings of complete $m$-ary trees, _Discrete Applied Math._ , 158 (2010) 507–515.
  * [13] D. Liu, Radio number for trees, _Discrete Math._ , 308 (2008), 1153–1164.
  * [14] D. Liu, L. Saha, S. Das, Improved lower bounds of the radio number of trees, _Theoretical Computer Science_ , 851 (2021), 1-13.
  * [15] D. Liu and M. Xie, Radio number of square cycles, _Congr. Numer._ , 169 (2004), 105–125.
  * [16] D. Liu and M. Xie, Radio number of square paths, _Ars Combin._ , 90 (2009), 307–319.
  * [17] D. Liu and X. Zhu, Multilevel distance labellings for paths and cycles, _SIAM J. Discrete Math._ , 19 (2005), 610–621.
  * [18] D. B. West, Introduction to graph theory, Prentice Hall, 2001.
  * [19] R. K. Yeh, A survey on labelling graphs with a condition at distance two, _Discrete Math._ , 306 (2006), 1217–1231.