# Radio Number for the Cartesian Product of Two Trees

Devsi Bantva
Department of Mathematics
Lukhdhirji Engineering College, Morvi - 363642
Gujarat, India
E-mail<EMAIL_ADDRESS>

Daphne Der-Fen Liu
California State University, Los Angeles, USA
E-mail<EMAIL_ADDRESS>Research is partially supported by the National
Science Foundation under grant DMS 1600773 and Cal State LA Properest Faculty
Fellow grant.

###### Abstract

Let $G$ be a simple connected graph. For any two vertices $u$ and $v$, let
$d(u,v)$ denote the distance between $u$ and $v$ in $G$, and let ${\rm
diam}(G)$ denote the diameter of $G$. A radio-labeling of $G$ is a function
$f$ which assigns to each vertex a non-negative integer (label) such that for
every distinct vertices $u$ and $v$ in $G$, it holds that
$|f(u)-f(v)|\mathchar 13374\relax{\rm diam}(G)-d(u,v)+1$. The span of $f$ is
the difference between the largest and smallest labels of $f(V)$. The radio
number of $G$, denoted by ${\rm rn}(G)$, is the smallest span of a radio
labeling admitted by $G$. In this paper, we give a lower bound for the radio
number of the Cartesian product of two trees. Moreover, we present three
necessary and sufficient conditions, and three sufficient conditions for the
product of two trees to achieve this bound. Applying these results, we
determine the radio number of the Cartesian product of two stars as well as a
path and a star.

_Keywords_ : Radio labeling; radio number; tree; Cartesian product of graphs.

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

##  1 Introduction

Radio labeling of graphs is motivated by the channel assignment introduced by
Hale [7]. In the channel assignment problem, the task is to assign a channel
to each of the given set of stations or transmitters so that interference is
avoided and the spectrum of the channels is minimized. The level of
interference between two stations are related to the proximity of their
locations. The closer the locations the stronger interference might occur. In
order to avoid stronger inference, the separation of the channels assigned to
the pair of stations has to be relatively larger.

One can model the above problem by representing each station by a vertex and
connecting two very close stations by an edge. A radio labeling of a graph $G$
is a mapping, $f:V(G)\to\mathbb{Z}^{+}$, so that the following holds for any
pair of distinct vertices:

$|f(u)-f(v)|\mathchar 13374\relax{\rm diam}(G)+1-d(u,v),$ (1)

where $d(u,v)$ is the distance between $u$ and $v$, and ${\rm diam}(G)$ is the
diameter of $G$. The span of $f$, denoted by ${\rm span}(f)$, is defined as
${\rm span}(f)=\max\\{|f(u)-f(v)|:u,v\in V(G)\\}$. The radio number of $G$ is

${\rm rn}(G)=\min\\{\ {\rm span}(f):f\mbox{ is a radio labeling of }G\\}.$

The notion of radio labeling was introduced by Chartrand et al. [5]. Since
then the radio number for special families of graphs has been studied widely
in the literature (cf. [3, 4, 9, 11]). The radio number of cycles and paths
were determined by Liu and Zhu [14]. Khennoufa and Togni [10] studied the
radio number for hypercubes by using generalized binary Gray codes. Ortiz et
al. [16] investigated the radio number of generalized prism graphs.
Niedzialomski [18] studied radio graceful graphs (where $G$ admits a
surjective radio labeling) and showed that the Cartesian product of $t$ copies
of a complete graph is radio graceful for certain $t$, providing infinitely
many examples of radio graceful graphs of arbitrary diameters. Zhou [20]
investigated the radio number for Cayley graphs. Recently, Bantva and Liu
discussed the radio number for block graphs and line graphs of trees in [2].
For positive integers $m,n\mathchar 13374\relax 3$, the toroidal grid
$G_{m,n}$ is the Cartesian product of cycles $C_{m}$ and $C_{n}$. Morris et
al. [17] determined ${\rm rn}(G_{n,n})$, Saha and Panigrahi [19] determined
${\rm rn}(G_{m,n})$ when $mn\equiv 0\pmod{2}$.

Moreover, the radio number of trees has been studied extensively. Liu [13]
proved a general lower bound for the radio number of trees, gave a necessary
and sufficient condition to achieve this bound. Later on, many families of
trees have been proved to achieve this bound, including complete $m$-ary trees
for $m\mathchar 13374\relax 3$ by Li et al. [12], level-wise regular trees
when all the internal vertices have degree at least 3 by Hàlasz and Tuza [8],
and banana trees, firecrackers trees and a special class of caterpillars by
Bantva et al. [1]. On the other hand, there exist trees whose radio number is
larger than this lower bound. For instance, odd paths [14], complete binary
trees [12], and some level-wise regular trees [6]. Recently, this lower bound
for those trees whose radio number does not reach the lower bound has been
improved by Liu et al. [15].

The aim of this paper is to extend the work on trees to the Cartesian product
of two trees. We prove a lower bound of the radio number for these graphs and
give three necessary and sufficient conditions as well as three sufficient
conditions for achieving this lower bound. Applying these results, we find the
radio numbers of the Cartesian products of two stars and a star with a path.

##  2 Preliminaries

In this section, we introduce definitions and known results that will be used
throughout the paper. Let $G$ be a simple finite connected graph. For two
vertices $u$ and $v$, the distance between $u$ and $v$ is the least length of
a path joining $u$ and $v$, denoted by $d_{G}(u,v)$. If $G$ is clear in the
context, we denote $d_{G}(u,v)$ by $d(u,v)$. The diameter of $G$ is ${\rm
diam}(G)=\max\\{d(u,v):u,v\in V(G)\\}$. The _weight_ of a graph $G$ on a
vertex $v\in V(G)$ is defined as $w_{G}(v)=\sum_{u\in V(G)}d(u,v)$. The
_weight of $G$_ is $w(G)=\min\\{w_{G}(v):v\in V(G)\\}$. A vertex $v\in V(G)$
is a _weight center_ of $G$ if $w_{G}(v)=w(G)$. We denote the set of weight
center(s) by $W(G)$. The following are proved in [13].

######  Lemma 2.1.

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

######  Lemma 2.2.

[13] Every tree $T$ has either one or two weight centers, and $T$ has two
weight centers, say $w$ and $w^{\prime}$, if and only if $ww^{\prime}$ is an
edge of $T$ and $T-ww^{\prime}$ consists of two equal-sized components.

Denote $P_{n}$ the $n$-vertex path. It can be easily seen that $P_{n}$ has two
weight centers if $n$ is even (the two middle vertices), and one weight center
when $n$ is odd (the middle vertex). An $n$-star, $n\mathchar 13374\relax 2$,
denoted by $K_{1,n}$, is a tree with one vertex adjacent to $n$ leaves
(degree-1 vertices). Apparently, the non-leaf vertex is the only weight center
of $K_{1,n}$.

We view a tree $T$ rooted at its weight center(s) $W(T)$. That is, if
$W(T)=\\{w\\}$ then $T$ is rooted at $w$; if $W(T)=\\{w,w^{\prime}\\}$ then
$T$ is rooted at both $w$ and $w^{\prime}$. Let $u,v\in V(T)$. If the unique
path joining $v$ and the nearest weight center to $v$ passes through $u$, then
$u$ is an _ancestor_ of $v$, and $v$ is a _descendent_ of $u$. Note that every
vertex is its own ancestor and descendent. If $v$ is a descendent of $u$ and
adjacent to $u$, then $v$ is called a _child_ of $u$, and $u$ the parent of
$v$.

######  Definition 1.

Let $u$ be a vertex adjacent to a weight center. The subtree induced by $u$
and all its descendent is called a _branch_ at $u$. If $u,v\not\in W(T)$ and
$u,v$ are adjacent to the same weight center, then the branches induced by $u$
and $v$ are called _different branches_. If $u$ and $v$ are adjacent to
different weight centers then the branches induced by $u$ and $v$ are called
_opposite branches_. Note that opposite branches occur only when $|W(T)|=2$.

######  Definition 2.

In a tree $T$, we say that vertices $x$ and $y$ belong to different branches
if $x$ and $y$ are in different branches, or one of them, say $x$, is a weight
center and the other is in the branch induced by a vertex adjacent to $x$. We
say that $x$ and $y$ are in opposite branches if $W(T)=\\{w,w^{\prime}\\}$ and
$x,y$ belong to different components of $T-ww^{\prime}$. That is, $w$ and
$w^{\prime}$ belong to opposite branches.

######  Definition 3.

Let $T$ be a tree. Define a _level function_
$L:V(T)\rightarrow\mathbb{N}\cup\\{0\\}$ by

$L_{T}(u):=\min\\{d(u,w):w\in W(T)\\}.$

The value $L_{T}(u)$ is called _level_ of $u$ in $T$. The _total level of $T$_
is defined as

$L(T):=\sum_{u\in V(T)}L_{T}(u).$

######  Definition 4.

Let $T$ be a tree. For any $u,v\in V(T)$, define

$\phi_{T}(u,v)=\max\\{L(z):z\ \mbox{is a common ancestor of $u$ and $v$}\\};$

$\delta_{T}(u,v)=\left\\{\begin{array}[]{ll}1&\mbox{if
$W(T)=\\{w,w^{\prime}\\}$, $u$ and $v$ belong to opposite
branches;}\\\\[5.69046pt] 0,&\mbox{ otherwise}.\end{array}\right.$

When it is clear in the context, we simply denote $L_{T}(u)$, $\phi_{T}(u,v)$,
and $\delta_{T}(u,v)$, by $L(u)$, $\phi(u,v)$, and $\delta(u,v)$,
respectively.

######  Lemma 2.3.

Let $T$ be a tree and $u,\;v\in V(T)$. The following hold:

  1. (a)

$0\mathchar 13366\relax\phi(u,v)\mathchar 13366\relax\max\\{L(x):x\in
V(T)\\}$.

  2. (b)

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

  3. (c)

The distance between two vertices $u$ and $v$ in $T$ is

$d(u,v)=L(u)+L(v)+\delta(u,v)-2\phi(u,v).$

######  Definition 5.

Let $G_{1}=(V(G_{1}),E(G_{1}))$ and $G_{2}=(V(G_{2}),E(G_{2}))$ be two graphs.
The _Cartesian product_ of $G_{1}$ and $G_{2}$, denoted by $G_{1}\Box G_{2}$,
is a graph with the vertex set $V(G_{1}\Box G_{2})=V(G_{1})\times V(G_{2})$,
where two vertices $(a,b)$ and $(c,d)$ are adjacent if $a=c$ and $bd\in
E(G_{2})$, or $b=d$ and $ac\in E(G_{1})$.

######  Observation 2.4.

Let $G$ and $H$ be graphs. The following hold:

  1. (a)

for any $u_{1},u_{2}\in V(G)$ and $v_{1},v_{2}\in V(H)$, $d_{G\Box
H}((u_{1},v_{1}),(u_{2},v_{2}))=d_{G}(u_{1},u_{2})+d_{H}(v_{1},v_{2})$;

  2. (b)

${\rm diam}(G\Box H)={\rm diam}(G)+{\rm diam}(H)$.

######  Lemma 2.5.

Let $T_{1}$ and $T_{2}$ be trees. Then $W(T_{1}\Box T_{2})=W(T_{1})\times
W(T_{2})$.

Proof Denote $G=T_{1}\Box T_{2}$. Consider the following cases.

Case-1: $|W(T_{1})|=|W(T_{2})|=1$. Denote $W(T_{1})=\\{w_{1}\\}$ and
$W(T_{2})=\\{w_{2}\\}$. It suffices to prove that for any $(u,v)\in V(G)$,
$w_{G}((u,v))\mathchar 13374\relax w_{G}((w_{1},w_{2}))$. Because
$w_{T_{1}}(u)\mathchar 13374\relax w_{T_{1}}(w_{1})$ and
$w_{T_{2}}(v)\mathchar 13374\relax w_{T_{2}}(w_{2})$, for any $u\in V(T_{1})$
and $v\in V(T_{2})$, we have

$\begin{array}[]{llll}w_{G}((u,v))&=&\sum_{x\in V(T_{1})}d(x,u)+\sum_{y\in
V(T_{2})}d(y,v)\\\ &=&w_{T_{1}}(u)+w_{T_{2}}(v)\mathchar 13374\relax
w_{T_{1}}(w_{1})+w_{T_{2}}(w_{2})=w_{G}((w_{1},w_{2})).\end{array}$

Case-2: $|W(T_{1})|\cdot|W(T_{2})|=2$. By symmetry, assume
$W(T_{1})=\\{w_{1}\\}$ and $W(T_{2})=\\{w_{2},w^{\prime}_{2}\\}$. Then
$w_{T_{1}}(w_{1})\mathchar 13366\relax w_{T_{1}}(u)$ and
$w_{T_{2}}(w_{2})=w_{T_{2}}(w^{\prime}_{2})\mathchar 13366\relax
w_{T_{2}}(v)$, for any $u\in V(T_{1})$ and $v\in V(T_{2})$. Let $(u,v)\in
V(G)$. Then

$\begin{array}[]{llll}w_{G}((u,v))&=&\sum_{x\in V(T_{1})}d(x,u)+\sum_{y\in
V(T_{2})}d(y,v)\\\ &=&w_{T_{1}}(u)+w_{T_{2}}(v)\mathchar 13374\relax
w_{T_{1}}(w_{1})+w_{T_{2}}(w_{2})=w_{T_{1}}(w_{1})+w_{T_{2}}(w^{\prime}_{2})=w_{G}((w_{1},w^{\prime}_{2})).\end{array}$

The case for $|W(T_{1})|=|W(T_{2})|=2$ can be proved similarly. The proof is
complete. $\Box$

Throughout the paper, for trees $T_{1}$ and $T_{2}$, we denote $G=T_{1}\Box
T_{2}$. For any $z_{a}=(x_{a},y_{a}),\;z_{b}=(x_{b},y_{b})\in V(G)$, define:

$\begin{array}[]{lll}L_{G}(z)&:=&L_{T_{1}}(x)+L_{T_{2}}(y)\\\
\phi_{G}((z_{a},z_{b}))&:=&\phi_{T_{1}}(x_{a},x_{b})+\phi_{T_{2}}(y_{a},y_{b}),\\\
\delta_{G}((z_{a},z_{b}))&:=&\delta_{T_{1}}(x_{a},x_{b})+\delta_{T_{2}}(y_{a},y_{b}).\end{array}$

We shall use simplified notations. For instance, we write the first in the
above by $L(z)=L(x)+L(y)$, etc. The distance between two vertices
$z_{a}=(x_{a},y_{a})$ and $z_{b}=(x_{b},y_{b})$ in $G$ is

$\displaystyle d(z_{a},z_{b})$ $\displaystyle=$ $\displaystyle
d((x_{a},y_{a}),(x_{b},y_{b}))=d(x_{a},x_{b})+d(y_{a},y_{b})$ (2)
$\displaystyle=$ $\displaystyle
L(x_{a})+L(x_{b})+L(y_{a})+L(y_{b})+\delta(x_{a},x_{b})+\delta(y_{a},y_{b})-2\phi(x_{a},x_{b})-2\phi(y_{a},y_{b})$
$\displaystyle=$ $\displaystyle
L(z_{a})+L(z_{b})+\delta(z_{a},z_{b})-2\phi(z_{a},z_{b}).$

Each $i=1,2$, the tree $T_{i}$ has $d(w_{i})$ branches if
$W(T_{i})=\\{w_{i}\\}$, and $d(w_{i})+d(w^{\prime}_{i})-2$ branches if
$W(T_{i})=\\{w_{i},w^{\prime}_{i}\\}$. Denote the branches of $T_{1}$ and
$T_{2}$ respectively by $T_{1,k}$ and $T_{2,k^{\prime}}$, $1\mathchar
13366\relax k\mathchar 13366\relax\beta_{1}$ and $1\mathchar 13366\relax
k^{\prime}\mathchar 13366\relax\beta_{2}$, where $\beta_{1}$ and $\beta_{2}$
are the numbers of branches of $T_{1}$ and $T_{2}$, respectively. Define a
_sector_ $S$ of vertices of $T_{1}\Box T_{2}$, where $S$ consisting of
vertices $(x_{a},y_{b})$ so that exactly one of the following holds for some
$1\mathchar 13366\relax k\mathchar 13366\relax\beta_{1}$ and $1\mathchar
13366\relax k^{\prime}\mathchar 13366\relax\beta_{2}$:

$\bullet$ $x_{a}\in V(T_{1,k}),y_{b}\in V(T_{2,k^{\prime}})$ $\bullet$
$x_{a}\in V(T_{1,k}),y_{b}=w_{2}$ $\bullet$ $x_{a}\in
V(T_{1,k}),y_{b}=w^{\prime}_{2}$

$\bullet$ $x_{a}=w_{1},y_{b}\in V(T_{2,k^{\prime}})$ $\bullet$
$x_{a}=w^{\prime}_{1},y_{b}\in V(T_{2,k^{\prime}})$ $\bullet$ $x_{a}\in
W(T_{1}),y_{b}\in W(T_{2})$.

Totally, $G$ has
$(|W(T_{1})|\times\beta_{2})+(\beta_{1}\times|W(T_{2})|)+\beta_{1}\beta_{2}+1$
sectors. Two sectors $S_{a}$ and $S_{b}$ are different, opposite, or separate
if for any $(x_{a},y_{a})\in S_{a}$ and $(x_{b},y_{b})\in S_{b}$ the following
hold:

  * •

_different_ : $x_{a}$ and $x_{b}$ as well as $y_{a}$ and $y_{b}$ are in
different branches of $T_{1}$ and $T_{2}$, respectively;

  * •

_opposite_ : $x_{a},x_{b}$ are in different branches of $T_{1}$, and
$y_{a},y_{b}$ are in opposite branches of $T_{2}$; or symmetrically
$x_{a},x_{b}$ are in opposite branches of $T_{1}$ and $y_{a},y_{b}$ are in
different branches of $T_{2}$;

  * •

_separate_ : $x_{a}$ and $x_{b}$ as well as $y_{a}$ and $y_{b}$ are in
opposite branches of $T_{1}$ and $T_{2}$.

######  Lemma 2.6.

Let $G=T_{1}\Box T_{2}$ be a Cartesian product of trees $T_{1}$ and $T_{2}$,
with orders $m$ and $n$ and diameter $d_{1}$ and $d_{2}$, respectively. Let
$p=mn$ and $d=d_{1}+d_{2}$. Then for any $z_{a}=(x_{a},y_{a}),\
z_{b}=(x_{b},y_{b})\in V(G)$, the following hold:

  1. (a)

$0\mathchar 13366\relax\phi(z_{a},z_{b})\mathchar 13366\relax\max\\{L(z):z\in
V(G)\\}$ and $0\mathchar 13366\relax\delta(z_{a},z_{b})\mathchar 13366\relax
2$;

  2. (b)

$\phi(z_{a},z_{b})=0$ if and only if $z_{a}$ and $z_{b}$ are in different,
opposite, or separate sectors;

  3. (c)

$\delta(z_{a},z_{b})=\left\\{\begin{array}[]{llll}0,&\mbox{if $z_{a}$ and
$z_{b}$ are in the same or different sectors,}\\\ 1,&\mbox{if $z_{a}$ and
$z_{b}$ are in opposite sectors,}\\\ 2,&\mbox{if $z_{a}$ and $z_{b}$ are in
separate sectors.}\end{array}\right.$

######  Lemma 2.7.

Let $T_{1}$ and $T_{2}$ be trees with $|W(T_{1})|=|W(T_{2})|=2$. For any
ordering $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(T_{1}\Box T_{2})$, the
following holds:

$\sum_{i=1}^{p-2}\delta(z_{i},z_{i+1})\mathchar 13366\relax 2p-3.$

Moreover, the equality holds if and only if $\delta(z_{(p/2)-1},z_{p/2})=1$;
and $\delta(z_{t},z_{t+1})=2$ otherwise.

Proof Denote
$W(T_{1})=\\{w_{1},w^{\prime}_{1}\\},W(T_{2})=\\{w_{2},w^{\prime}_{2}\\},$ and

$\begin{array}[]{lllll}W_{i}&=&\\{v\in V(T_{i}):\mbox{$v$ is in the same
component as $w_{i}$ in $T_{i}-w_{i}w^{\prime}_{i}$}\\},&i=1,2;\\\
W^{\prime}_{i}&=&\\{v^{\prime}\in V(T_{i}):\mbox{$v^{\prime}$ is in the same
component as $w^{\prime}_{i}$ in
$T_{i}-w_{i}w^{\prime}_{i}$}\\},&i=1,2.\end{array}$

By Lemma 2.2, $|W_{1}|=|W^{\prime}_{1}|=m/2$ and
$|W_{2}|=|W^{\prime}_{2}|=n/2$. Further, $V(G)$ is partitioned into four
equal-size subsets denoted by: $A=W_{1}\times W_{2}$, $B=W^{\prime}_{1}\times
W_{2}$, $C=W^{\prime}_{1}\times W^{\prime}_{2}$, and $D=W_{1}\times
W^{\prime}_{2}$. By definition, two vertices $z_{a},z_{b}\in V(G)$ have
$\delta(z_{a},z_{b})=2$ if and only if $(z_{a},z_{b})\in(A\times
C)\cup(C\times A)\cup(B\times D)\cup(D\times B)$. Note, $|A\times C|=|B\times
D|$.

By Lemma 2.6 (a), $\sum_{i=1}^{p-2}\delta(z_{i},z_{i+1})\mathchar 13366\relax
2p-2$. Assume to the contrary, $\sum_{i=1}^{p-2}\delta(z_{i},z_{i+1})=2p-2$.
That is, $\delta(z_{i},z_{i+1})=2$ for all $0\mathchar 13366\relax i\mathchar
13366\relax p-2$. Without loss of generality, assume $z_{0}\in A$. Since
$\delta(z_{0},z_{1})=2$, it must be $z_{1}\in C$. Similarly, as
$\delta(z_{1},z_{2})=2$, $z_{2}\in A$. Continue this process, we have
$z_{i}\in A$ if $i$ is even; $z_{i}\in C$ if $i$ is odd. This is impossible,
as it covers at most half of the vertices in $G$. Hence, the result follows.
$\Box$

######  Definition 6.

Let $T_{1}$ and $T_{2}$ be trees. Two vertices $z_{a}$ and $z_{b}$ of
$V(T_{1}\Box T_{2})$ are called feasible if $z_{a}$ and $z_{b}$ are in
different sectors when $|W(T_{1}\Box T_{2})|=1$, opposite sectors when
$|W(T_{1}\Box T_{2})|=2$, and separate sectors when $|W(T_{1}\Box T_{2})|=4$;
and non-feasible otherwise.

######  Definition 7.

An ordering $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(T_{1}\Box T_{2})$ is
called feasible if for every $0\mathchar 13366\relax t\mathchar 13366\relax
q-2$, $z_{t}$ and $z_{t+1}$ are feasible, except for the case when
$|W(T_{1}\Box T_{2})|=4$ and $t=(p/2)-1$ for which $z_{(p/2)-1}$ and $z_{p/2}$
are in opposite sectors. Note that if $\vec{V}$ is feasible and $|W(T_{1}\Box
T_{2})|=4$, by Lemma 2.7, $\sum_{t=1}^{p-2}\delta(z_{t},z_{t+1})=2p-3$.

##  3 Main Results

A radio labeling $f$ of a graph $G$ is an injective mapping. By shifting the
labels, we may assume $f(v)=0$ for some vertex $v$. Thus, $f$ induces an
ordering $\vec{V}_{f}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$, where

$0=f(z_{0})<f(z_{1})<\ldots<f(z_{p-1})={\rm span}(f).$

######  Theorem 3.1.

Let $G=T_{1}\Box T_{2}$, where $T_{1}$ and $T_{2}$ are trees with orders $m$
and $n$, and diameters $d_{1}$ and $d_{2}$, respectively. Denote $mn=p$ and
$d=d_{1}+d_{2}$. Then

${\rm rn}(G)\mathchar
13374\relax\left\\{\begin{array}[]{ll}(p-1)(d+1)-2nL(T_{1})-2mL(T_{2})+1,&\mbox{
if $|W(T_{1})|=|W(T_{2})|=1$},\\\\[5.69046pt]
(p-1)d-2nL(T_{1})-2mL(T_{2}),&\mbox{ if
$|W(T_{1})|\cdot|W(T_{2})|=2$,}\\\\[5.69046pt]
(p-1)(d-1)-2nL(T_{1})-2mL(T_{2})+1,&\mbox{ if
$|W(T_{1})|=|W(T_{2})|=2$}.\\\\[5.69046pt] \end{array}\right.$ (3)

Moreover, the equality in Eq. 3 holds if and only if there exists a feasible
ordering $(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$ such that the following
hold:

  1. (a)

$L(z_{0})+L(z_{p-1})=1$ if $|W(G)|=1$, and $L(z_{0})+L(z_{p-1})=0$ if
$|W(G)|\mathchar 13374\relax 2$;

  2. (b)

the following mapping $f$ is a radio labeling for $G$:

$f(z_{0})=0;f(z_{i+1})=f(z_{i})+d+1-L(z_{i})-L(z_{i+1})-\delta(z_{i},z_{i+1}),0\mathchar
13366\relax i\mathchar 13366\relax p-2.$ (4)

Proof Suppose that $f$ is a radio labeling of $G$ with the ordering
$\vec{V}_{f}=(z_{0},z_{1},\ldots,z_{p-1})$. By definition, $f$ satisfies the
inequality $f(z_{i+1})-f(z_{i})\mathchar 13374\relax d+1-d(z_{i},z_{i+1})$ for
all $0\mathchar 13366\relax i\mathchar 13366\relax p-2$. Summing up these
$p-1$ inequalities,

${\rm span}(f)=f(z_{p-1})\mathchar
13374\relax(p-1)(d+1)-\sum_{t=0}^{p-2}d(z_{t},z_{t+1}).$ (5)

Denote $z_{t}=(x_{i_{t}},y_{j_{t}})$, $0\mathchar 13366\relax t\mathchar
13366\relax p-1$, where $x_{i_{t}}\in V(T_{1})$ and $y_{j_{t}}\in V(T_{2})$.
By Eq. (2),

$\displaystyle\sum_{t=0}^{p-2}d(z_{t},z_{t+1})$ $\displaystyle=$
$\displaystyle\sum_{t=0}^{p-2}[L(x_{i_{t}})+L(x_{i_{t+1}})+L(y_{j_{t}})+L(y_{j_{t+1}})+\delta(x_{i_{t}},x_{i_{t+1}})+\delta(y_{j_{t}},y_{j_{t+1}})$
(6) $\displaystyle-2\phi(x_{i_{t}},x_{i_{t+1}})-2\phi(y_{j_{t}},y_{j_{t+1}})]$
$\displaystyle=$ $\displaystyle
2nL(T_{1})+2mL(T_{2})-L(x_{i_{0}})-L(x_{i_{p-1}})-L(y_{j_{0}})-L(y_{j_{p-1}})$
$\displaystyle+\sum_{t=0}^{p-2}\left[\delta(z_{t},z_{t+1})-2\phi(x_{i_{t}},x_{i_{t+1}})-2\phi(y_{j_{t}},y_{j_{t+1}})\right]$

We proceed the proof by three cases.

Case-1: $|W(T_{1})|=|W(T_{2})|=1$. Then
$\delta(x_{i_{t}},x_{i_{t+1}})=\delta(y_{j_{t}},y_{j_{t+1}})=0$ for all $i,j$.
Because $|W(G)|=1$, so
$L(x_{i_{0}})+L(x_{i_{p-1}})+L(y_{j_{0}})+L(y_{j_{p-1}})\mathchar 13374\relax
1$. As $\phi(x,y)\mathchar 13374\relax 0$, for any $x,y$:

$\sum_{t=0}^{p-2}d(z_{t},z_{t+1})\mathchar 13366\relax
2nL(T_{1})+2mL(T_{2})-1.$

Substituting the above to Eq. 5, we obtain

${\rm span}(f)=f(z_{p-1})\mathchar
13374\relax(p-1)(d+1)-2nL(T_{1})-2mL(T_{2})+1.$

Case-2: $|W(T_{1})|\cdot|W(T_{2})|=2$. By symmetry, assume $|W(T_{1})|=1$ and
$|W(T_{2})|=2$. In this case, $\delta(x_{i_{t}},x_{i_{t+1}})=0$ and
$0\mathchar 13366\relax\delta(y_{j_{t}},y_{j_{t+1}})\mathchar 13366\relax 1$
for $0\mathchar 13366\relax t\mathchar 13366\relax p-2$. Hence
$\delta(z_{i},z_{i+1})\mathchar 13366\relax 1$ for all $i$. Further, since
$|W(G)|=2$, it holds that
$L(x_{i_{0}})+L(x_{i_{p-1}})+L(y_{j_{0}})+L(y_{j_{p-1}})\mathchar 13374\relax
0$. Hence,

$\sum_{t=0}^{p-2}d(z_{t},z_{t+1})\mathchar 13366\relax
2nL(T_{1})+2mL(T_{2})+(p-1).$

Similarly, the result follows by substituting the above into Eq. 5.

Case-3: $|W(T_{1})|=|W(T_{2})|=2$. As $G$ has four weight centers, it holds
that $L(x_{i_{0}})+L(x_{i_{p-1}})+L(y_{j_{0}})+L(y_{j_{p-1}})\mathchar
13374\relax 0$. By Lemma 2.7, $\sum_{i=0}^{p-1}\delta(z_{i},z_{i+1})\mathchar
13366\relax 2p-3$. Hence

$\sum_{t=0}^{p-2}d(z_{t},z_{t+1})\mathchar 13366\relax
2nL(T_{1})+2mL(T_{2})+2p-3.$

The results follows by substituting the above into Eq. 5.

It is clear that the equality holds in Eq. 3 if and only if all the qualities
hold in Eq. 1 as well as the ones in the above, which are reflected on the
moreover part. $\Box$

It is easy to see that ${\rm rn}(P_{2}\Box P_{2})$ is equal to the lower bound
in Eq. 3. Indeed, this is the only possibility that the lower bound of ${\rm
rn}(T_{1}\Box T_{2})$ in Theorem 3.1 is sharp when $|W(T_{1}\Box T_{2})|=4$.

######  Theorem 3.2.

Let $T_{1}$ and $T_{2}$ be trees of orders $m,n$ and diameters $d_{1},d_{2}$,
respectively. Suppose $|W(T_{1})|=|W(T_{2})|=2$. Then the equality in Eq. 3
holds only if $T_{1}=T_{2}=P_{2}$.

Proof Let $T_{1}$ and $T_{2}$ be trees that satisfy the hypotheses. Denote
$G=T_{1}\Box T_{2}$. Since $|W(T_{1})|=|W(T_{2})|=2$, $m$ and $n$ are even, so
$p$ is even. Assume to the contrary that it is not the case that
$T_{1}=T_{2}=P_{2}$ but ${\rm rn}(G)=(p-1)(d-1)-2nL(T_{1})-2mL(T_{2})+1$. By
Theorem 3.1, there exists a feasible ordering $(z_{0},z_{1},\ldots,z_{p-1})$
of $V(G)$ such that Theorem 3.1 (a) (b) are satisfied. Since ${\rm
diam}(G)=d\mathchar 13374\relax 4$ (as $G\neq P_{2}\Box P_{2}$) and
$d(w,w^{\prime})\mathchar 13366\relax 2$ for any $w,w^{\prime}\in W(G)$, there
exist vertices $z_{x}$ and $z_{y}$ in separate or opposite sectors where
$L(z_{x}),L(z_{y})\mathchar 13374\relax\frac{d-2}{2}$ and
$\\{x,y\\}\neq\\{\frac{p}{2}-2,\frac{p}{2}\\}$. Hence, there exists $z_{t}\in
V(G)$ such that $L(z_{t})\mathchar 13374\relax\frac{d-2}{2}$ and
$t-1,t+1\neq\frac{p}{2}-1$. Consider $z_{t-1}$ and $z_{t+1}$ for Eq. 4. By
Theorem 3.1 (b) and $\delta(z_{t-1},z_{t})=\delta(z_{t},z_{t+1})=2$, we arrive
at the following contradiction:

$\begin{array}[]{lll}f(z_{t+1})-f(z_{t-1})&=&2(d+1)-4-L(z_{t-1})-2L(z_{t})-L(z_{t+1})\\\
&\mathchar 13366\relax&2(d+1)-4-L(z_{t-1})-2(\frac{d-2}{2})-L(z_{t+1})\\\
&=&d-L(z_{t-1})-L(z_{t+1})\\\ &<&d+1-d(z_{t-1},z_{t+1})\ \ \ \mbox{($\mathchar
13354\relax d(z_{t-1},z_{t+1})\mathchar 13366\relax
L(z_{t-1})+L(z_{t+1}))$}.\hskip 43.36243pt\Box\\\ \end{array}.$

In the next two results, we give additional necessary and sufficient
conditions for $T_{1}\Box T_{2}$ to achieve the lower bound in Theorem 3.1.

######  Theorem 3.3.

Let $G=T_{1}\Box T_{2}$, where $T_{1}$ and $T_{2}$ are trees with orders $m$
and $n$, and diameters $d_{1}$ and $d_{2}$, respectively. Let $p=mn$ and
$d=d_{1}+d_{2}$. Then the equality of Eq. 3 holds if and only if there exists
a feasible ordering $\vec{V}=(z_{0},\ldots,z_{p-1})$ of $V(G)$ such that the
following hold:

  1. (a)

$L(z_{0})+L(z_{p-1})=1$ when $|W(G)|=1$, and $L(z_{0})+L(z_{p-1})=0$ when
$|W(G)|\mathchar 13374\relax 2$;

  2. (b)

for any two vertices $z_{a},z_{b}\;(0\mathchar 13366\relax a<b\mathchar
13366\relax p-1)$ the following is satisfied

$d(z_{a},z_{b})\mathchar
13374\relax\sum_{t=a}^{b-1}\left[L(z_{t})+L(z_{t+1})+\delta(z_{t},z_{t+1})\right]-(b-a-1)(d+1).$
(7)

Proof Necessity: Suppose that the equality of Eq. 3 holds. By Theorem 3.1,
there exists an optimal radio labeling $f$ of $G$ with a feasible ordering
$\vec{V}$ of $V(G)$ such that (a) and (b) in Theorem 3.1 hold. For any two
vertices $z_{a}$ and $z_{b}\;(0\mathchar 13366\relax a<b\mathchar 13366\relax
p-1)$ in $\vec{V}$, we have

$f(z_{b})-f(z_{a})=\sum_{t=a}^{b-1}\left[d+1-L(z_{t})-L(z_{t+1})-\delta(z_{t},z_{t+1})\right].$

Since $f$ is a radio labeling of $G$, $f(z_{b})-f(z_{a})\mathchar 13374\relax
d+1-d(z_{a},z_{b})$. Substituting this to the above, Eq. 7 is obtained. Hence
(b) is true.

Sufficiency: Let $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ be an ordering
satisfying (a) and (b). It is clear that $\vec{V}$ is feasible. By Theorem 3.1
it suffices to prove that the mapping $f$ defined by Eq. 4 on $\vec{V}$ is a
radio labeling. Let $z_{a}$ and $z_{b}\;(0\mathchar 13366\relax a<b\mathchar
13366\relax p-1)$ be two arbitrary vertices. By Eq. 4 and (b), we obtain

$f(z_{b})-f(z_{a})=(b-a)(d+1)-\sum_{t=a}^{b-1}\left[L(z_{t})+L(z_{t+1})+\delta(z_{t},z_{t+1})\right]\mathchar
13374\relax d+1-d(z_{a},z_{b}).$

Hence $f$ is a radio labeling for $G$. The proof is complete. $\Box$

For integers $x\mathchar 13366\relax y$, denote $[x,y]=\\{x,x+1,\cdots,y\\}$.

######  Theorem 3.4.

Let $G=T_{1}\Box T_{2}$, where $T_{1}$ and $T_{2}$ are trees with orders $m$
and $n$, and diameters $d_{1}\mathchar 13374\relax 2$ and $d_{2}\mathchar
13374\relax 2$, respectively. Let $p=mn$ and $d=d_{1}+d_{2}$. Denote
$\xi=|W(T_{1})|+|W(T_{2})|-2$. Then the equality of Eq. 3 holds if and only if
there exists a feasible order $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$
such that all the following hold:

  1. (a)

$L(z_{0})+L(z_{p-1})=1$ when $|W(G)|=1$, and $L(z_{0})+L(z_{p-1})=0$ when
$|W(G)|\mathchar 13374\relax 2$;

  2. (b)

$L(z_{s})\mathchar 13366\relax\frac{d+1-2\xi}{2}$ for all $0\mathchar
13366\relax s\mathchar 13366\relax p-1$, except when $|W(G)|=4$ and
$s\in\\{(p/2)-1,p/2\\}$, for which $L(z_{s})\mathchar
13366\relax\frac{d+3-2\xi}{2}$;

  3. (c)

any two non-feasible vertices $z_{a}$ and $z_{b}\;(0\mathchar 13366\relax
a<b\mathchar 13366\relax p-1)$ satisfy

$\phi(z_{a},z_{b})\mathchar
13366\relax\left\\{\begin{array}[]{lll}(b-a-1)\left(\frac{d+1-\xi}{2}\right)-\sum\limits_{t=a+1}^{b-1}L(z_{t})-\left(\frac{\xi-\delta(z_{a},z_{b})-1}{2}\right),&\mbox{if
$|W(G)|=4$ and}\\\ &\mbox{$\\{(p/2)-1,p/2\\}\subseteq[a,b]$},\\\
(b-a-1)\left(\frac{d+1-\xi}{2}\right)-\sum\limits_{t=a+1}^{b-1}L(z_{t})-\left(\frac{\xi-\delta(z_{a},z_{b})}{2}\right),&\mbox{otherwise.}\end{array}\right.$

Moreover, with conditions (a), (b), (c), the mapping defined by Eq. 4 is an
optimal radio labeling of $G$.

Proof Necessity: Suppose the equality of Eq. 3 holds. By Theorem 3.3, there
exists a feasible order $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$ such
that Theorem 3.3 (a) (b) hold. By Theorem 3.3 (a),
$L(z_{0}),L(z_{p-1})\mathchar 13366\relax 1$. If $d_{1}=d_{2}=2$, then
$|W(T_{1})|=|W(T_{2})|=1$ and $\xi=0$. So, $L(z_{0}),L(z_{p-1})\mathchar
13366\relax 1\mathchar 13366\relax(d+1-2\xi)/2$. These inequalities also hold
for other cases.

For $1\mathchar 13366\relax s\mathchar 13366\relax(p-2)$, applying Eq. 7 to
$d(z_{s-1},z_{s+1})$ and by Eq. (2), we obtain

$2L(z_{s})\mathchar 13366\relax
d+1-\delta(z_{s-1},z_{s})-\delta(z_{s},z_{s+1})+\delta(z_{s-1},z_{s+1})-2\phi(z_{s-1},z_{s+1}).$
(8)

Since $\vec{V}$ is feasible, $\delta(z_{s},z_{s+1})=\xi$ and
$\delta(z_{s-1},z_{s+1})=0$ for all $0\mathchar 13366\relax s\mathchar
13366\relax p-2$, except when $|W(G)|=4$ and $s\in\\{(p/2)-1,p/2\\}$.
Substituting this (without the exceptional case) into Eq. 8, we have
$2L(z_{s})\mathchar 13366\relax d+1-2\xi.$ When $|W(G)|=4$ and
$s\in\\{(p/2)-1,p/2\\}$, we have
$\delta(z_{s-1},z_{s})+\delta(z_{s},z_{s+1})=2\xi-1=3$ and
$\delta(z_{s-1},z_{s+1})=1$. Substituting this into Eq. 8, we get
$2L(z_{s})\mathchar 13366\relax d+3-2\xi.$ Thus, (b) is true.

To prove (c), assume $z_{a}$ and $z_{b}$ are non-feasible vertices. Combining
Eq. (2) and Eq. 7,

$\delta(z_{a},z_{b})-2\phi(z_{a},z_{b})\mathchar 13374\relax
2\sum_{t=a+1}^{b-1}L(z_{t})+\sum_{t=a}^{b-1}\delta(z_{t},z_{t+1})-(b-a-1)(d+1).$

Since $\vec{V}$ is feasible, $\delta(z_{t},z_{t+1})=\xi$ for all $0\mathchar
13366\relax t\mathchar 13366\relax p-2$, except when $|W(G)|=4$ and
$t=(p/2)-1$, in which $\delta(z_{(p/2)-1},z_{p/2})=\xi-1$. Substituting all
these into the above, (c) is satisfied.

Sufficiency: Suppose there exists a feasible order
$\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$ such that (a)-(c) hold. It
suffices to prove that Eq. 7 in Theorem 3.3 is true for any $z_{a}$ and
$z_{b}$, $0\mathchar 13366\relax a<b\mathchar 13366\relax p-1$. Denote the
right-hand side of (7) by $S_{a,b}$.

Assume $z_{a}$ and $z_{b}$ are feasible vertices. Then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})+\delta(z_{a},z_{b})$. As $\vec{V}$ is
feasible, $\delta(z_{a},z_{b})=\delta(z_{a},z_{a+1})$. When $|W(G)|=4$,
$\delta(z_{a},z_{a+1})=1$ occurs only when $a=(p/2)-1$. In this case,
$\delta(z_{a},z_{b})=1$ for all $b\mathchar 13374\relax a$. Thus, it also
holds that $\delta(z_{a},z_{b})=\delta(z_{a},z_{a+1})$.

By (b), $2L(z_{t})+\delta(z_{t},z_{t+1})-(d+1)\mathchar 13366\relax 0$. Hence

$\begin{array}[]{lll}S_{a,b}&=&L(z_{a})+L(z_{b})+\delta(z_{a},z_{a+1})+\sum\limits_{t=a+1}^{b-1}\left[2L(z_{t})+\delta(z_{t},z_{t+1})-(d+1)\right]\\\
&\mathchar
13366\relax&L(z_{a})+L(z_{b})+\delta(z_{a},z_{a+1})=L(z_{a})+L(z_{b})+\delta(z_{a},z_{b})=d(z_{a},z_{b}).\end{array}$

If $z_{a}$ and $z_{b}$ are non-feasible vertices, as $\vec{V}$ is feasible,
Eq. 7 can be obtained by (c). The proof is complete. $\Box$

In the next result, we give three sufficient conditions for the lower bound
given in Eq. 3 to be tight when $|W(T_{1})|\cdot|W(T_{2})|\mathchar
13366\relax 2$.

######  Theorem 3.5.

Let $G=T_{1}\Box T_{2}$, where $T_{1}$ and $T_{2}$ are trees of orders $m$ and
$n$, and diameters $d_{1}$ and $d_{2}$, respectively, and
$|W(T_{1})|\cdot|W(T_{2})|\mathchar 13366\relax 2$. Denote $p=mn$,
$d=d_{1}+d_{2}$, and $\xi=|W(T_{1})|+|W(T_{2})|-2$. Then equality of Eq. 3
holds if there exists a feasible order $\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$
of $V(G)$ such that the following are true:

  1. (a)

$L(z_{0})+L(z_{p-1})=1$ when $|W(G)|=1$, and $L(z_{0})+L(z_{p-1})=0$ when
$|W(G)|\mathchar 13374\relax 2$,

  2. (b)

any of the following conditions holds:

    1. (i)

$\min\\{d(z_{t},z_{t+1}),d(z_{t+1},z_{t+2})\\}\mathchar
13366\relax\frac{d+\xi}{2}$, for all $0\mathchar 13366\relax t\mathchar
13366\relax p-3$,

    2. (ii)

$d(z_{t},z_{t+1})\mathchar 13366\relax\frac{d+\xi+2}{2}$, for all $0\mathchar
13366\relax t\mathchar 13366\relax p-2$,

    3. (iii)

$L(z_{s})\mathchar 13366\relax\frac{d+1-\xi}{2}$, for all $0\mathchar
13366\relax s\mathchar 13366\relax p-1$; and if $b-a<d$ then $z_{a}$ and
$z_{b}$ are in different or opposite sectors.

Proof We prove that if there exists a feasible order
$\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$ such that (a) and one of
(b.i), (b.ii), (b.iii) holds, then $\vec{V}$ satisfies Theorem 3.3 (a) (b).
Since (a) is the same as Theorem 3.3 (a), it suffices to prove that Theorem
3.3 (b) is true for any two vertices $z_{a}$ and $z_{b}$, $0\mathchar
13366\relax a<b\mathchar 13366\relax p-1$. Denote the right-hand side of Eq. 7
by $S_{a,b}$.

Case-1: $|W(T_{1})|=|W(T_{2})|=1$. In this case, $\xi=0$ and
$\delta(z_{t},z_{t+1})=0$ for all $0\mathchar 13366\relax t\mathchar
13366\relax p-1$.

Subcase 1.1: Suppose (a) and (b.i) hold. By (b.i) and as $\vec{V}$ is
feasible, for each $1\mathchar 13366\relax t\mathchar 13366\relax p-2$,
$L(z_{t})\mathchar
13366\relax\min\\{L(z_{t-1})+L(z_{t}),L(z_{t})+L(z_{t+1})\\}=\min\\{d(z_{t-1},z_{t}),d(z_{t},z_{t+1})\\}\mathchar
13366\relax d/2$.

Let $z_{a}$ and $z_{b}$ be two arbitrary vertices. If $z_{a}$ and $z_{b}$ are
feasible, then $d(z_{a},z_{b})=L(z_{a})+L(z_{b})$,

$\begin{array}[]{lll}S_{a,b}&=&L(z_{a})+L(z_{b})+2\left[\sum\limits_{t=a+1}^{b-1}L(z_{t})\right]-(b-a-1)(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{b})-(b-a-1)\mathchar 13366\relax
L(z_{a})+L(z_{b})=d(z_{a},z_{b}).\end{array}$

Assume $z_{a}$ and $z_{b}$ are non-feasible. Then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})$. If $b-a\mathchar
13374\relax 4$, by (b.i), $d(z_{a+1},z_{a+2})\mathchar 13366\relax d/2$ or
$d(z_{a+2},z_{a+3})\mathchar 13366\relax d/2$. In either case,
$2[(L(z_{a+1})+L(z_{a+2})+L(z_{a+3})]\mathchar 13366\relax 2d$. Thus,

$\begin{array}[]{llll}S_{a,b}&\mathchar
13366\relax&L(z_{a})+L(z_{b})+2[(L(z_{a+1})+L(z_{a+2})+L(z_{a+3})]-3(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{b})-d-3\\\
&=&L(z_{a})+L(z_{b})-2((d+3)/2)\\\ &\mathchar
13366\relax&L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})\ \ (\mathchar
13354\relax\phi(z_{a},z_{b})\mathchar
13366\relax\min\\{L(z_{a}),L(z_{b})\\}).\end{array}$

Suppose $b-a=3$. Assume
$\max\\{d(z_{a},z_{a+1}),d(z_{a+1},z_{a+2})\\}\mathchar 13366\relax d/2$.
Similarly to the above, we get $S_{a,b}\mathchar 13366\relax
L(z_{a})+L(z_{b})-d-2=L(z_{a})+L(z_{b})-2((d+2)/2)\mathchar 13366\relax
L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b})$. Assume
$\max\\{d(z_{a},z_{a+1}),d(z_{a+1},z_{a+2})\\}>d/2$. Without loss of
generality, suppose $d(z_{a},z_{a+1})<d(z_{a+1},z_{a+2})$. Recall
$L(z_{a+2})\mathchar 13366\relax d/2$. By (b.i), $L(z_{a+1})\mathchar
13366\relax d/2-L(z_{a})$, implying

$\begin{array}[]{llll}S_{a,b}&=&L(z_{a})+L(z_{a+3})+2[L(z_{a+1})+L(z_{a+2})]-2(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{a+3})-2L(z_{a})\\\ &\mathchar
13366\relax&L(z_{a})+L(z_{a+3})-2\phi(z_{a},z_{a+3})=d(z_{a},z_{b}).\end{array}$

Finally, assume $b-a=2$. By (b.i), $L(z_{a})+L(z_{a+1})\mathchar 13366\relax
d/2$ or $L(z_{a+1})+L(z_{a+2})\mathchar 13366\relax d/2$. Without loss of
generality, assume $L(z_{a})+L(z_{a+1})\mathchar 13366\relax d/2$, implying
$S_{a,b}\mathchar 13366\relax L(z_{a})+L(z_{a+2})-2(L(z_{a})+1)$ $\mathchar
13366\relax L(z_{a})+L(z_{a+2})-2\phi(z_{a},z_{a+2})=d(z_{a},z_{a+2})$.

Subcase 1.2: Suppose (a) and (b.ii) hold. If $b-a=1$, then $z_{a}$ and $z_{b}$
are feasible vertices. Hence, $S_{a,b}=L(z_{a})+L(z_{b})=d(z_{a},z_{b})$, so
Eq. 7 is satisfied. If $b-a\mathchar 13374\relax 2$, by (b.ii),
$d(z_{t},z_{t+1})=L(z_{t})+L(z_{t+1})\mathchar 13366\relax(d+2)/2$ for
$a\mathchar 13366\relax t\mathchar 13366\relax b-1$. Hence

$S_{a,b}\mathchar 13366\relax\sum_{t=a}^{b-1}((d+2)/2)-(b-a-1)(d+1)\mathchar
13366\relax 1\mathchar 13366\relax d(z_{a},z_{b}).$

Thus Eq. 7 is satisfied.

Subcase 1.3: Suppose (a) and (b.iii) hold. Assume $z_{a}$ and $z_{b}$ are
feasible vertices. If $b=a+1$, the result follows. Assume $b\mathchar
13374\relax a+2$. Then $d(z_{a},z_{b})=L(z_{a})+L(z_{b})$ and
$S_{a,b}=L(z_{a})+L(z_{b})+2\sum_{t=a+1}^{b-1}L(z_{t})-(b-a-1)(d+1)\mathchar
13366\relax L(z_{a})+L(z_{b})+2((d+1)/2)-(b-a-1)(d+1)\mathchar 13366\relax
L(z_{a})+L(z_{b})=d(z_{a},z_{b})$.

If $z_{a}$ and $z_{b}$ are not feasible, then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})$. Assume $d$ is even. By
(b.iii), $L(z_{t})\mathchar 13366\relax d/2$ for $0\mathchar 13366\relax
t\mathchar 13366\relax p-1$. By the second part of (b.iii), $S_{a,b}\mathchar
13366\relax L(z_{a})+L(z_{b})-(b-a-1)\mathchar 13366\relax
L(z_{a})+L(z_{b})-2((d-1)/2)\mathchar 13366\relax
L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b})$. Assume $d$ is odd. By
(b.iii), $L(z_{t})\mathchar 13366\relax(d+1)/2$ for $0\mathchar 13366\relax
t\mathchar 13366\relax p-1$. As $\max\\{L(z_{t})+L(z_{t+1}):0\mathchar
13366\relax t\mathchar 13366\relax p-2\\}\mathchar 13366\relax d$,

$2\sum_{t=a+1}^{b-1}L(z_{t})\mathchar
13366\relax(b-a-1)\left[(d+1)/2\right]+(b-a-1)\left[(d-1)/2\right].$

Hence, we have

$\begin{array}[]{llll}S_{a,b}&=&L(z_{a})+L(z_{b})+2\left[\sum\limits_{t=a+1}^{b-1}L(z_{t})\right]-(b-a-1)(d+1)\\\
&\mathchar
13366\relax&L(z_{a})+L(z_{b})+(b-a-1)\left[(d+1)/2\right]+(b-a-1)\left[(d-1)/2)\right]-(b-a-1)(d+1)\\\
&=&L(z_{a})+L(z_{b})-(b-a-1)\\\ &\mathchar
13366\relax&L(z_{a})+L(z_{b})-2((d-1)/2)\ \ \ \mbox{(by the second part of
(b.iii))}\\\ &\mathchar
13366\relax&L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b}).\end{array}$

Case-2: $|W(T_{1})|\cdot|W(T_{2})|=2$. Then $\xi=1$. Without loss of
generality, assume $|W(T_{1})|=1$ and $|W(T_{2})|=2$. As $\vec{V}$ is
feasible, $\delta(z_{t},z_{t+1})=1$ for all $0\mathchar 13366\relax t\mathchar
13366\relax p-1$.

Subcase 2.1: Suppose (a) and (b.i) hold. Since $\vec{V}$ is feasible,
$d(z_{t},z_{t+1})=L(z_{t})+L(z_{t+1})+1$ for all $t$. By (b.i),
$L(z_{t})\mathchar
13366\relax\min\\{L(z_{t-1})+L(z_{t}),L(z_{t})+L(z_{t+1})\\}=\min\\{d(z_{t-1},z_{t})-1,d(z_{t},z_{t+1})-1\\}\mathchar
13366\relax(d-1)/2$ for $1\mathchar 13366\relax t\mathchar 13366\relax p-2$.

Let $z_{a}$ and $z_{b}$ be vertices. If $z_{a}$ and $z_{b}$ are feasible, then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})+1$. Thus,

$\begin{array}[]{llll}S_{a,b}&=&L(z_{a})+L(z_{b})+1+\sum\limits_{t=a+1}^{b-1}(2L(z_{t})+1)-(b-a-1)(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{b})+1-(b-a-1)\mathchar 13366\relax
L(z_{a})+L(z_{b})+1=d(z_{a},z_{b}).\end{array}$

If $z_{a}$ and $z_{b}$ are non-feasible, then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})$. If $b-a\mathchar
13374\relax 4$, then by (b.i), $L(z_{a})+L(z_{a+1})\mathchar
13366\relax(d-1)/2$ or $L(z_{a+1})+L(z_{a+2})\mathchar 13366\relax(d-1)/2$.
This implies, $2[L(z_{a+1})+L(z_{a+2})+L(z_{a+3})]\mathchar 13366\relax
2(d-1)$. Hence, $S_{a,b}\mathchar 13366\relax L(z_{a})+L(z_{b})-(d+1)\mathchar
13366\relax L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b})$.

Suppose $b-a=3$. If $\max\\{d(z_{a},z_{a+1}),d(z_{a+1},z_{a+2})\\}\mathchar
13366\relax(d+1)/2$, then $L(z_{a+1})+L(z_{a+2})\mathchar 13366\relax(d-1)/2$.
Hence,

$\begin{array}[]{llll}S_{a,b}&=&L(z_{a})+L(z_{b})+3+2[L(z_{a+1})+L(z_{a+2})]-2(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{b})-d\mathchar 13366\relax
L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b}).\end{array}$

Assume $\max\\{d(z_{a},z_{a+1}),d(z_{a+1},z_{a+2})\\}>(d+1)/2$. Without loss
of generality, let $d(z_{a},z_{a+1})<d(z_{a+1},z_{a+2})$. By (b.i),
$L(z_{a+1})\mathchar 13366\relax(d-1)/2-L(z_{a})$. Hence,

$S_{a,b}\mathchar 13366\relax L(z_{a})+L(z_{b})-2L(z_{a})-1\mathchar
13366\relax L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b}).$

Finally, assume $b-a=2$. Then $L(z_{a})+L(z_{a+1})\mathchar
13366\relax(d-1)/2$ or $L(z_{a+1})+L(z_{a+2})\mathchar 13366\relax(d-1)/2$.
Without loss of generality, assume $L(z_{a})+L(z_{a+1})\mathchar
13366\relax(d-1)/2$. Then

$S_{a,b}\mathchar 13366\relax L(z_{a})+L(z_{b})-2L(z_{a})\mathchar 13366\relax
L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b}).$

Subcase-2.2: Suppose (a) and (b.ii) hold. If $b-a=1$, then $z_{a}$ and $z_{b}$
are feasible vertices. So $S_{a,b}=L(z_{a})+L(z_{b})+1=d(z_{a},z_{b})$. If
$b-a\mathchar 13374\relax 3$, by (b.ii),
$d(z_{t},z_{t+1})=L(z_{t})+L(z_{t+1})+1\mathchar 13366\relax(d+3)/2$ for all
$0\mathchar 13366\relax t\mathchar 13366\relax b-1$. Hence $S_{a,b}\mathchar
13366\relax\sum_{t=a}^{b-1}((d+3)/2)-(b-a-1)(d+1)\mathchar
13366\relax(3(d+3)/2)-2(d+1)\mathchar 13366\relax 0<d(z_{a},z_{b})$.

Assume $b-a=2$. If $d(z_{a},z_{a+2})\mathchar 13374\relax 2$, then
$S_{a,a+2}\mathchar 13366\relax(d+3)-(d+1)=2\mathchar 13366\relax
d(z_{a},z_{a+2})$. If $d(z_{a},z_{a+2})=1$, as $z_{a}=(x_{i_{a}},y_{j_{a}})$
and $z_{a+2}=(x_{i_{a+2}},y_{j_{a+2}})$, either $x_{i_{a}}=x_{i_{a+2}}$ and
$d_{T_{2}}(y_{j_{a}},y_{j_{a+2}})=1$, or $y_{j_{a}}=y_{j_{a+2}}$ and
$d_{T_{1}}(x_{i_{a}},x_{i_{a+2}})=1$. Assume $x_{i_{a}}=x_{i_{a+2}}$ and
$d_{T_{2}}(y_{j_{a}},y_{j_{a+2}})=1$. Then direct calculation shows that
$|d(z_{a},z_{a+1})-d(z_{a+1},z_{a+2})|=1$. Combining with (b.ii),
$\min\\{d(z_{a},z_{a+1}),d(z_{a+1},z_{a+2})\\}\mathchar 13366\relax(d+1)/2$,
which implies, $S_{a,a+2}\mathchar
13366\relax(d+3)/2+(d+1)/2-(d+1)=1=d(z_{a},z_{b})$. Thus, Eq. 7 is satisfied.

Subcase-2.3: Suppose (a) and (b.iii) hold. If $z_{a}$ and $z_{b}$ are feasible
vertices then $d(z_{a},z_{b})=L(z_{a})+L(z_{b})+1$ and
$S_{a,b}=L(z_{a})+L(z_{b})+1+\sum_{t=a+1}^{b-1}(2L(z_{t})+1)-(b-a-1)(d+1)\mathchar
13366\relax
L(z_{a})+L(z_{b})+1+\sum_{t=a+1}^{b-1}(2(d/2)+1)-(b-a-1)(d+1)=L(z_{a})+L(z_{b})+1=d(z_{a},z_{b})$.
If $z_{a}$ and $z_{b}$ are non-feasible then
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})$. Assume $d$ is even.
Then $L(z_{t})\mathchar 13366\relax d/2$ for all $t\in[0,p-1]$. Since
$\max\\{L(z_{t})+L(z_{t+1}):t\in[0,p-2]\\}=\max\\{d(z_{t},z_{t+1})-1:t\in[0,p-2]\\}\mathchar
13366\relax d-1$, it is impossible that $L(z_{t})=L(z_{t+1})=d/2$. Thus,

$\sum_{t=a+1}^{b-1}(2L(z_{t})+1)\mathchar
13366\relax\frac{(b-a-1)(d+1)}{2}+\frac{(b-a-1)(d-1)}{2}=(b-a-1)d.$

Hence

$\begin{array}[]{llll}S_{a,b}&=&L(z_{a})+L(z_{b})+\sum\limits_{t=a+1}^{b-1}\left[2L(z_{t})+1\right]-(b-a-1)(d+1)\\\
&\mathchar 13366\relax&L(z_{a})+L(z_{b})-(b-a-1)\\\ &\mathchar
13366\relax&L(z_{a})+L(z_{b})-(d-1)\ \ \ \mbox{(by the second part of
(b.iii))}\\\ &\mathchar 13366\relax&L(z_{a})+L(z_{b})-2\left[(d-1)/2\right]\\\
&\mathchar
13366\relax&L(z_{a})+L(z_{b})-2\phi(z_{a},z_{b})=d(z_{a},z_{b}).\end{array}$

Suppose $d$ is odd. By (b.iii), $L(z_{t})\mathchar 13366\relax(d-1)/2$ for all
$t\in[0,p-1]$. Similar to the above, we get $S_{a,b}\mathchar 13366\relax
L(z_{a})+L(z_{b})-(b-a-1)$. The result follows by the same calculation above.
$\Box$

##  4 Sharpness of the Bounds

In this section, we determine the radio number of some Cartesian products of
two trees using Theorems 3.1 to 3.4.

######  Theorem 4.1.

Let $m\mathchar 13374\relax n\mathchar 13374\relax 3$ be integers. Then ${\rm
rn}(K_{1,m}\Box K_{1,n})=mn+3(m+n)+1$.

Proof Denote $G=K_{1,m}\Box K_{1,n}$. Then $p=|E(G)|=(m+1)(n+1)$, ${\rm
diam}(G)=4$, $|W(G)|=1$, $L(K_{1,m})=m$, and $L(K_{1,n})=n$. Substituting
these into Eq. 3, we obtain the lower bound for ${\rm rn}(G)$. We prove that
the bound is attained by giving a feasible ordering
$\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ of $V(G)$ satisfying the conditions of
Theorem 3.3.

Denote $V(K_{1,m})=\\{x_{0},x_{1},\ldots,x_{m}\\}$,
$E(K_{1,m})=\\{x_{0}x_{i}:1\mathchar 13366\relax i\mathchar 13366\relax m\\}$,
$V(K_{1,n})=\\{y_{0},y_{1},\ldots,y_{n}\\}$, and
$E(K_{1,n})=\\{y_{0}y_{i}:1\mathchar 13366\relax i\mathchar 13366\relax n\\}$.
Define an ordering of $V(G)$ as follows: For $(i,j)\in[0,m]\times[0,n]$, let
$z_{t}=(x_{i},y_{j})$, where

$t:=\left\\{\begin{array}[]{ll}(i-j)(n+1)+j,&\mbox{ if $i\mathchar 13374\relax
j$},\\\\[5.69046pt] (m+2+i-j)(n+1)-i-1,&\mbox{ if $i<j$}.\end{array}\right.$

See Fig. 1 for an example. It is easy to see that the given ordering is
feasible and $L(z_{0})+L(z_{p-1})=1$. It suffices to prove $\vec{V}$ satisfies
Theorem 3.3 (b), by showing that Eq. 7 is satisfied. Let $z_{a}$ and $z_{b}$
be two arbitrary vertices, $0\mathchar 13366\relax a<b\mathchar 13366\relax
p-1$. Denote the right-hand side of (7) by $S_{a,b}$. Since ${\rm diam}(G)=4$,
and for all $0\mathchar 13366\relax t\mathchar 13366\relax p-2$,
$L(z_{t})\mathchar 13366\relax 2$ and $\delta(z_{t},z_{t+1})=0$, we have

$S_{a,b}=\sum\limits_{t=a}^{b-1}(L(z_{t})+L(z_{t+1}))-5(b-a-1)\mathchar
13366\relax 4(b-a)-5(b-a-1)=5-(b-a).$

If $b-a\mathchar 13374\relax 4$, then $S_{a,b}\mathchar 13366\relax 1\mathchar
13366\relax d(z_{a},z_{b})$. If $b-a=3$, then our labeling ordering has
$d(z_{a},z_{b})\mathchar 13374\relax 2$, hence $S_{a,b}\mathchar 13366\relax
2\mathchar 13366\relax d(z_{a},z_{b})$.

Assume $b-a=2$. Let $C=\\{z_{t}=(x_{i_{t}},y_{j_{t}}):x_{i_{t}}=x_{0}\mbox{ or
}y_{j_{t}}=y_{0}\\}$. If $z_{a}=z_{0}\in C$, then $d(z_{0},z_{2})=2$ and
$S_{a,b}=1<d(z_{0},z_{2})$. If $z_{a}\neq z_{0}$, then either
$|\\{z_{a},z_{b}\\}\cap C|=1$ or $|\\{z_{a},z_{a+1},z_{b}\\}\cap C|=0$. The
former has $d(z_{a},z_{b})\mathchar 13374\relax 3$, the latter has
$d(z_{a},z_{b})\mathchar 13374\relax 4$, and for both $S_{a,b}\mathchar
13366\relax d(z_{a},z_{b})$. If $b-a=1$, since $\vec{V}$ is feasible, it holds
$d(z_{a},z_{b})=L(z_{a})+L(z_{b})$. Hence,
$S_{a,b}=L(z_{a})+L(z_{b})=d(z_{a},z_{b})$. Therefore, Eq. 7 is satisfied. The
proof is complete. $\Box$

Figure 1: An ordering (left) and an optimal radio labeling (right) of
$K_{1,6}\Box K_{1,4}$

######  Theorem 4.2.

Let $m,n\mathchar 13374\relax 3$ be integers. Then

${\rm rn}(P_{m}\Box
K_{1,n})=\left\\{\begin{array}[]{ll}\frac{1}{2}\left[m^{2}(n+1)+2m+n-1\right],&\mbox{
if $m$ is odd},\\\\[5.69046pt]
\frac{1}{2}\left[m^{2}(n+1)+2(m-1)\right],&\mbox{ if $m$ is
even}.\end{array}\right.$ (9)

Proof Denote $G=P_{m}\Box K_{1,n}$. Then $p=|V(G)|=m(n+1)$, diam$(G)=m+1$,
$|W(G)|=1$ if $m$ is odd, and $|W(G)|=2$ if $m$ is even. As $L(K_{1,n})=n$,
$L(P_{m})=\frac{m^{2}-1}{4}$ if $m$ is odd, and $L(P_{m})=\frac{m(m-2)}{4}$ if
$m$ is even, we obtain the right-hand side of (9) as a lower bound for ${\rm
rn}(G)$ by substituting these into (3).

Next we give a feasible ordering $\vec{V}=(z_{0},z_{1},\cdots,z_{p-1})$ for
$V(G)$, satisfying Theorem 3.3 when $m$ is odd, and satisfying Theorem 3.5
when $m$ is even. Denote $V(P_{m})=\\{x_{1},x_{2},\ldots,x_{m}\\}$,
$E(P_{m})=\\{x_{i}x_{i+1}:i\in[1,m-1]\\}$, $V(K_{1,n})=\\{y_{i}:i\in[0,n]\\}$,
and $E(K_{1,n})=\\{y_{0}y_{j}:j\in[1,n]\\}$.

Case-1: $m$ is odd. Denote $m^{\prime}=(m+1)/2$. Then
$W(G)=\\{(x_{m^{\prime}},y_{0})\\}$. Define $\vec{V}$ by two steps:

Step 1. For $t\in[0,3n+2]$, define $z_{t}:=(x_{i},y_{j})$,
$i\in\\{1,m^{\prime},m\\}$ and $j\in[0,n]$:

Subcase-1: $n\equiv 0$ (mod $3$).

$t:=\left\\{\begin{array}[]{lll}3n+2,&\mbox{$i=1$ and $j=0$},\\\\[5.69046pt]
n+j-1,&\mbox{$i=1$ and $j>0$ and $j\equiv 0$ (mod 3); or $i=m$ and $j\equiv 2$
(mod 3)},\\\ 2n+j+1,&\mbox{$i=1$ and $j\equiv 1$ (mod 3); or $i=m^{\prime}$
and $j\equiv 2$ (mod 3)},\\\ j,&\mbox{$i=1$ and $j\equiv 2$ (mod 3); or
$i=m^{\prime}$ and $j\equiv 0$ (mod 3);}\\\ &\hskip 14.45377pt\mbox{or $i=m$
and $j\equiv 1$ (mod 3)},\\\ n+j+2,&\mbox{$i=m^{\prime}$ and $j\equiv 1$ (mod
3)},\\\ 3n+1,&\mbox{$i=m$ and $j=0$},\\\ 2n+j-2,&\mbox{$i=m$ and $j>0$ and
$j\equiv 0$ (mod 3)}.\\\ \end{array}\right.$

Subcase-2: $n\equiv 1$ (mod $3$).

$t:=\left\\{\begin{array}[]{ll}3n+2,&\mbox{$i=1$ and $j=0$},\\\ 6\lfloor
n/3\rfloor+j+2,&\mbox{$i=1$ and $j>0$ and $j\equiv 0$ (mod 3); or
$i=m^{\prime}$ and $j\equiv 1$ (mod 3);}\\\ &\hskip 14.45377pt\mbox{or $i=m$
and $j\equiv 2$ (mod 3)},\\\ 3\lfloor n/3\rfloor+j+1,&\mbox{$i=1$ and $j\equiv
1$ (mod 3); or $i=m^{\prime}$ and $j\equiv 2$ (mod 3);}\\\ &\hskip
14.45377pt\mbox{or $i=m$ and $j>0$ and $j\equiv 0$ (mod 3)},\\\ j,&\mbox{$i=1$
and $j\equiv 2$ (mod 3); or $i=m^{\prime}$ and $j\equiv 0$ (mod 3);}\\\
&\hskip 14.45377pt\mbox{or $i=m$ and $j\equiv 1$ (mod 3)},\\\
3n+1,&\mbox{$i=m$ and $j=0$}.\\\ \end{array}\right.$

Subcase-3: $n\equiv 2$ (mod $3$).

$t:=\left\\{\begin{array}[]{ll}3n+2,&\mbox{$i=1$ and $j=0$},\\\\[5.69046pt]
3\lfloor n/3\rfloor+j+2,&\mbox{$i=1$ and $j>0$ and $j\equiv 0$ (mod 3); or
$i=m^{\prime}$ and $j\equiv 1$ (mod 3);}\\\ &\mbox{\hskip 14.22636ptor $i=m$
and $j\equiv 2$ (mod 3)},\\\\[5.69046pt] 6\lfloor n/3\rfloor+j+4,&\mbox{$i=1$
and $j\equiv 1$ (mod 3); or $i=m^{\prime}$ and $j\equiv 2$ (mod 3)};\\\
&\mbox{\hskip 14.22636ptor $i=m$ and $j>0$ and $j\equiv 0$ (mod
3)},\\\\[5.69046pt] j,&\mbox{$i=1$ and $j\equiv 2$ (mod 3); or $i=m^{\prime}$
and $j\equiv 0$ (mod 3);}\\\ &\mbox{\hskip 14.22636ptor $i=m$ and $j\equiv 1$
(mod 3)},\\\\[5.69046pt] 3n+1,&\mbox{$i=m$ and $j=0$}.\\\\[5.69046pt]
\end{array}\right.$

Step 2. For $t\in[3(n+1),p-1]$, set $z_{t}:=(x_{i},y_{j})$, $i\in[2,m-1]$,
$i\neq m^{\prime}$, $j\in[0,n]$, where

$t:=\left\\{\begin{array}[]{ll}(2i+1)(n+1)-1,&\mbox{$i\in[2,m^{\prime}-1]$,
$j=0$},\\\\[5.69046pt] 3(n+1)+2\lceil
n/2\rceil+2(i-2)(n+1)+j-1,&\mbox{$i\in[2,m^{\prime}-1]$, $j$ is even and
$j\neq 0$},\\\\[5.69046pt] 3(n+1)+2(i-2)(n+1)+j,&\mbox{$i\in[2,m^{\prime}-1]$,
$j$ is odd},\\\\[5.69046pt] (2i-m)(n+1),&\mbox{$i\in[m^{\prime}+1,m-1]$,
$j=0$},\\\\[5.69046pt] 3(n+1)+(2i-m-3)(n+1)+j,&\mbox{$i\in[m^{\prime}+1,m-1]$,
$j$ is even and $j\neq 0$},\\\\[5.69046pt] 3(n+1)+2\lfloor
n/2\rfloor+(2i-m-3)(n+1)+j+1,&\mbox{$i\in[m^{\prime}+1,m-1]$, $j$ is
odd}.\end{array}\right.$

Observe that the above defined ordering $\vec{V}$ is feasible and
$L(z_{0})+L(z_{p-1})=1$. It suffices to show that $\vec{V}$ satisfies Eq. 7
for Theorem 3.3 (b). Let $z_{a}$ and $z_{b}$ be two arbitrary vertices,
$0\mathchar 13366\relax a<b\mathchar 13366\relax p-1$. Denote the right-hand
side of (7) by $S_{a,b}$. Assume $b-a\mathchar 13374\relax 3$. For any $t$,
among the three values in $\\{d(z_{t},z_{t+1}):t\in[a,a+2]\\}$, two are at
most $(d+2)/2$, and the remaining one is at most $d$. Thus,

$\begin{array}[]{llll}S_{a,b}&\mathchar
13366\relax&\left[2(b-a)/3\right]\left[(d+2)/2\right]+\left[(b-a)/3\right]d-(b-a)(d+1)+d+1\\\
&=&\left[(b-a)/3\right](-d-1)+d+1\mathchar 13366\relax
0<d(z_{a},z_{b}).\end{array}$

Assume $b-a=2$. If $a\in[0,3n-2]$. Suppose $a\equiv 0$ (mod $3$). By the
defined ordering we have $d/2\mathchar 13366\relax
d(z_{a},z_{a+1})=L(z_{a})+L(z_{a+1})\mathchar
13366\relax(d+2)/2,d(z_{a+1},z_{b})=L(z_{a+1})+L(z_{b})=d$ and
$d(z_{a},z_{b})=(d+2)/2$. Hence, $S_{a,b}\mathchar 13366\relax
d/2<d(z_{a},z_{b})$. If $a\equiv 1$ (mod $3$), then
$d(z_{a},z_{a+1})=L(z_{a})+L(z_{a+1})=d$,
$d(z_{a+1},z_{b})=L(z_{a+1})+L(z_{b})=(d+2)/2$ and $d(z_{a},z_{b})=(d+2)/2$.
Hence $S_{a,b}=d/2<d(z_{a},z_{b})$. If $a\equiv 2$ (mod $3$), then
$d(z_{t},z_{t+1})=L(z_{t})+L(z_{t+1})=(d+2)/2$ for $t=a,a+1$, and
$d(z_{a},z_{b})=d$. Hence, $S_{a,b}=1<d(z_{a},z_{b})$.

If $a=3n-1$, then $d(z_{a},z_{a+1})=L(z_{a})+L(z_{a+1})=(d+2)/2$,
$d(z_{a+1},z_{b})=L(z_{a+1})+L(z_{b})=d/2$ and $d(z_{a},z_{b})=d-1$. Hence
$S_{a,b}=0<d(z_{a},z_{b})$. If $a=3n$, then
$d(z_{a},z_{a+1})=L(z_{a})+L(z_{a+1})=d/2$,
$d(z_{a+1},z_{b})=L(z_{a+1})+L(z_{b})=d-2$ and $d(z_{a},z_{b})=d/2$. Hence,
$S_{a,b}=(d/2)-3<d(z_{a},z_{b})$. If $a=3n+1$, then $d(z_{a},z_{a+1})=d-2$,
$d(z_{a+1},z_{b})=d/2$ and $d(z_{a},z_{b})=d/2-2$. Again, $S_{a,b}\mathchar
13366\relax(d/2)-3<d(z_{a},z_{b})$.

If $3n+2\mathchar 13366\relax a\mathchar 13366\relax p-1$, then
$d(z_{t},z_{t+1})\mathchar 13366\relax(d+2)/2$ for $t=a,a+1$ and
$d(z_{a},z_{b})\mathchar 13374\relax 1$. Hence, $S_{a,b}\mathchar 13366\relax
1\mathchar 13366\relax d(z_{a},z_{b})$. Thus, Eq. 7 of Theorem 3.3 (b) is
satisfied.

Case-2: $m$ is even. Denote $m=2m^{\prime}$. Recall that
$W(P_{m})=\\{x_{m^{\prime}},x_{m^{\prime}+1}\\}$, and $|W(P_{m}\Box
K_{1,n})|=2$. Then $\xi=1$. Define an ordering
$\vec{V}=(z_{0},z_{1},\ldots,z_{p-1})$ by:

$t:=\left\\{\begin{array}[]{ll}2(m^{\prime}-i)(n+1)+2\lfloor
n/2\rfloor+j+1,&\mbox{$i\in[1,m^{\prime}]$ and $j$ is odd},\\\\[5.69046pt]
2(m^{\prime}-i)(n+1)+j,&\mbox{$i\in[1,m^{\prime}]$, $j$ is
even},\\\\[5.69046pt] 2(m-i)(n+1)+j,&\mbox{$i\in[m^{\prime}+1,m]$ and $j$ is
odd},\\\\[5.69046pt] 2(m-i)(n+1)+2\lceil
n/2\rceil+j-1,&\mbox{$i\in[m^{\prime}+1,m]$, $j$ is even and $j\neq
0$},\\\\[5.69046pt] 2(m-i+1)(n+1)-1,&\mbox{$i\in[m^{\prime}+1,m]$ and
$j=0$}.\end{array}\right.$

Observe that the ordering $\vec{V}$ defined above is feasible and satisfies
conditions (a) and (b)-(ii) of Theorem 3.5, that is,
$d(z_{t},z_{t+1})\mathchar 13366\relax(d+\xi+2)/2=(m+4)/3$ holds for all $t$.
$\Box$

Figures 2-5 provide examples for labellings in Theorem 4.2.

Figure 2: An optimal ordering and an optimal radio labeling of $P_{5}\Box
K_{1,3}$

Figure 3: An optimal ordering and an optimal radio labeling of $P_{5}\Box
K_{1,4}$

Figure 4: An optimal ordering and an optimal radio labeling of $P_{5}\Box
K_{1,5}$

Figure 5: An optimal ordering and an optimal radio labeling of $P_{6}\Box
K_{1,5}$

## References

  * [1] D. Bantva, S. Vaidya and S. Zhou, Radio number of trees, Discrete Appl. Math., 217 (2017), 110–122.
  * [2] D. Bantva and D. Liu, Optimal radio labelings of block graphs and line graphs of trees, Theor. Comput. Sci., 891 (2021), 90–104.
  * [3] K. F. Benson, M. Porter and M. Tomova, The radio number of all graphs of order $n$ and diameter $n-2$, Le Mathematiche, 68 (2013), 167–190.
  * [4] R. C$\check{\mbox{a}}$da, J. Ekstein, P. Holub and O. Togni, Radio labeling of distance graphs, Discrete Appl. Math., 161(18) (2013), 2876–2884.
  * [5] G. Chartrand, D. Erwin and F. Harary, A graph labeling suggested by FM channel restrictions, Bull. Inst. Combin. Appl., 43 (2005), 43–57.
  * [6] A. Chavez, D. Liu and M. Shurman, Optimal radio $k$-labelings of trees. Eur. J. Comb., 91 (2021), 103203.
  * [7] W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, 68(12), 1980, 1497–1514.
  * [8] V. Halàsz and Z. Tuza, Distance-constrained labeling of complete trees, Discrete Math., 338 (2015), 1398–1406.
  * [9] J. van den Heuvel, R. Leese and M. Shepherd, Graph labeling and radio channel assignment, J. Graph Theory, 29 (1998), 263–283.
  * [10] R. Khennoufa and O. Togni, The radio antipodal and radio numbers of the hypercube, Ars Combin., 102 (2011), 447–461.
  * [11] D. Král, The channel assignment problem with variable weights, SIAM J. Discrete Math., 20 (2006), 690–704.
  * [12] X. Li, V. Mak and S. Zhou, Optimal radio labelings of complete $m$-ary tree, Discrete Appl. Math., 178 (2014), 109–120.
  * [13] D. Liu, Radio number for trees, Discrete Math., 308 (2008), 1153–1164.
  * [14] D. Liu and X. Zhu, Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math., 19 (2005), 610–621.
  * [15] D. Liu, L. Saha and S. Das, Improved lower bound for the radio number of trees, Theor. Comput. Sci., 851 (2021), 1–13.
  * [16] P. Martinez, J. Ortiz, M. Tomova and C. Wyels, Radio numbers for generalized prism graphs, Discuss. Math. Graph Theory, 31 (2011), 45–62.
  * [17] M. Morris-Rivera, M. Tomova, C. Wyels and A. Yeager, The radio number of $C_{n}\mathchar 1027\relax C_{n}$, Ars Combin., 120 (2015), 7–21.
  * [18] A. Niedzialomski, Radio graceful Hamming graphs, Discuss. Math. Graph Theory, 36 (2016), 1007–1020.
  * [19] L. Saha and P. Panigrahi, On the radio number of toroidal grids, Australas. J. Combin., 55 (2013), 273–288.
  * [20] S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theoret. Comput. Sci., 310 (2004), 501–511.