Radio number of the cartesian product of a tree and a complete graph

Vasoya, Payal; Bantva, Devsi

doi:10.61091/cn235-05

Abstract

1. Introduction
2. Preliminaries
3. A tight lower bound for rn(TKn)
4. Radio number of the Cartesian product of a level-wise regular tree and a complete graph
5. Concluding remarks
Acknowledgement
Statements and declarations

References

Congressus Numerantium

Volume 235
Pages: 47-64

Research article

Radio number of the cartesian product of a tree and a complete graph

^¹, ^²

¹Gujarat Technogical University, Ahmedabad – 382 424, Gujarat, India

²Lukhdhirji Engineering College, Morvi 363 642, Gujarat, India

Received: 30/05/2024
Accepted: 31/01/2025
Published: 11/02/2025

Copyright Link
License

Abstract

A radio labeling of a graph $G$ is a mapping $f : V (G) \to {0, 1, 2, \dots}$ such that $| f (u) - f (v) | \geq diam (G) + 1 - d (u, v)$ for every pair of distinct vertices $u, v$ of $G$ , where $diam (G)$ is the diameter of $G$ and $d (u, v)$ is the distance between $u$ and $v$ in $G$ . The radio number $rn (G)$ of $G$ is the smallest integer $k$ such that $G$ admits a radio labeling $f$ with $max {f (v) : v \in V (G)} = k$ . In this paper, we give a lower bound for the radio number of the Cartesian product of a tree and a complete graph and give two necessary and sufficient conditions for the sharpness of the lower bound. We also give three sufficient conditions for the sharpness of the lower bound. We determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph which attains the lower bound. The radio number of the Cartesian product of a path and a complete graph derived in [B. M. Kim, W. Hwang, and B. C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim., 30 (2015), 139–149] can be obtained using our results in a short way.

Keywords: radio labelling, radio number, cartesian product, tree, complete graph

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; the closer the location, the stronger the interference might occur. In order to avoid stronger interference, the larger frequency gap between two assigned frequencies must be required. In [10], Hale designed the optimal labelling problem for graphs to deal with this channel assignment problem. In this model, the transmitters are represented by the vertices of a graph, and two vertices are adjacent if the corresponding transmitters are close to each other. Initially, only two levels of interference, namely avoidable and unavoidable, were considered which inspired Griggs and Yeh [8] to introduce the following concept: An $L (2, 1)$ -labelling of a graph $G$ is a function $f : V (G) \to {0, 1, 2, \dots}$ 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 $λ$ -number (or the $λ_{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 $d i a m (G)$ (the diameter of a graph $G$ is $d i a m (G) = max {d (u, v) : u, v \in V (G)}$ ). In [7,6], Chartrand et al. introduced the concept of the radio labelling problem by extending the condition on distance in $L (2, 1)$ -labelling from two to the maximum possible distance in a graph, namely the diameter of a graph.

Definition 1.1. A radio labelling of a graph

G

is a mapping

f : V (G) \to {0, 1, 2, \dots}

such that the following hold for every pair of distinct vertices

u, v

G

\begin{matrix} (1) & | f (u) - f (v) | \geq d i a m (G) + 1 - d (u, v) . \end{matrix}

The integer

f (u)

is called the label of

u

under

f

, and the span of

f

is defined as

s p a n (f) = max {| f (u) - f (v) | : u, v \in V (G)}

. The radio number of

G

is defined as

r n (G) = min_{f} s p a n (f)

with minimum taken over all radio labellings

f

G

. A radio labelling

f

G

is called optimal if

s p a n (f) = r n (G)

Observe that the radio labelling problem is a min-max type optimization problem. Without loss of generality, we may always assume that any radio labelling assigns $0$ to some vertex so that the span of a radio labelling is equal to the maximum label used. Since $d (u, v) \leq d i a m (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 $\begin{matrix} (2) & {\vec{V}}_{f} : a_{0}, a_{1}, \dots, a_{m - 1}, \end{matrix}$ of the vertices of $G$ such that $\begin{matrix} (3) & 0 = f (a_{0}) < f (a_{1}) < \dots < f (a_{m - 1}) = s p a n (f) . \end{matrix}$ A linear order $a_{0}, a_{1}, \dots, a_{m - 1}$ of $V (T)$ is called an optimal linear order if it induced by some optimal radio labelling $f$ of $T$ .

Determining the radio number of graphs is a tough and challenging task. The radio number is known only for very few graphs and much attention has been paid to special families of graphs. It turns out that even for some special graph families the problem may be difficult. For example, the radio number of paths was determined by Liu and Zhu in [17], and even for this basic graph family the problem is nontrivial. In [15,16], Liu and Xie determine the radio number for the square graph of paths and cycles. In [4], Benson et al. determined the radio number of all graphs of order $n \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 for achieving the lower bound. The authors gave three other sufficient conditions for achieving the lower bound and also discuss the radio number of line graphs of trees and block graphs in [2]. Using these results, the authors determine the radio number of extended star of blocks and level-wise regular block graphs in [2].

In this paper, we give a lower bound for the radio number of the Cartesian product of a path and a complete graph (Theorem 3.1). We also give two necessary and sufficient conditions (Theorems 3.2 and 3.3) and three other sufficient conditions (Theorem 3.4) for achieving the lower bound. Using these results, we determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph. The radio number of the Cartesian product of a path and a complete graph given in [11] can be obtained using our results in a short way.

2. Preliminaries

We follow [17] for standard graph-theoretic terms and notations. In a graph $G$ , the neighbourhood of any $v \in V (G)$ is $N_{G} (v) = {u : u 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 $d i a m (G)$ , is $d i a m (G) = max {d_{G} (u, v) : u, v \in V (G)}$ . We drop the suffix in above-defined terms when $G$ is clear in the context. A complete graph $K_{n}$ is a graph on $n$ vertices in which any two vertices are adjacent. A tree is a connected acyclic graph. We fix $V (T) = {u_{0}, u_{1}, \dots, u_{m - 1}}$ for tree $T$ of order $m$ and $V (K_{n}) = {v_{0}, v_{1}, \dots, 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^{'}}

if and only if

r r^{'}

is an edge of

T

and

T - r r^{'}

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) ∖ W (T)$ be a vertex adjacent to a weight center $x$ . The subtree of $T$ induced by $u$ and all its descendants is called the branch of $T$ at $u$ . Two vertices $u, v$ of $T$ are said to be in different branches if the path between them contains only one weight center and in opposite branches if the path joining them contains two weight centers. We view a tree $T$ rooted at its weight center $W (T)$ : if $W (T) = {r}$ , then $T$ is rooted at $r$ ; if $W (T) = {r, r^{'}}$ , then $T$ is rooted at $r$ and $r^{'}$ in the sense that both $r$ and $r^{'}$ are at level 0. In either case, for each $u \in V (T)$ , define $L (u) = 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 $ϕ (u, v) = max {L (x) : x is a common ancestor of u and v},$ $δ (u, v) = {\begin{cases} 1, & if | W (T) | = 2 and the (u, v) -path in T containsboth weight centers, \\ 0, & 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:

(a) $ϕ (u, v) \geq 0$ ;

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

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

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

$\begin{matrix} (4) & d (u, v) = L (u) + L (v) - 2 ϕ (u, v) + δ (u, v) . \end{matrix}$

Define $ε (T) = {\begin{cases} 1, & if | W (T) | = 1, \\ 0, & 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 H$ with $V (G H) = V (G) \times V (H)$ such that two vertices $(a, b)$ and $(c, d)$ are adjacent if $a = c$ and $(b, d) \in E (H)$ or $b = d$ and $(a, c) \in E (G)$ . It is clear from the definition that $d_{G 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}

(a) $| V (T K_{n}) | = m n$ , and

(b) $d i a m (T K_{n}) = d i a m (T) + 1$ .

Let $\vec{V} = (w_{0}, w_{1}, \dots, w_{m n - 1})$ be an ordering of $V (T K_{n})$ , where $| T | = m$ . Then each $w_{t} (0 \leq t \leq m n - 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, \dots, m - 1$ appears $n$ times and each vertex $v_{j}, j = 0, 1, \dots, n - 1$ appears $m$ times in $T K_{n}$ . For $w_{a} = (u_{i_{a}}, v_{j_{a}}), w_{b} = (u_{i_{b}}, v_{j_{b}}) \in V (T K_{n}) (0 \leq a, b \leq m n - 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 K_{n}) (0 \leq a, b \leq m n - 1)$ , the distance between $w_{a}$ and $w_{b}$ is given by $\begin{matrix} (5) & d (w_{a}, w_{b}) = L (u_{i_{a}}) + L (u_{i_{b}}) + δ (u_{i_{a}}, u_{i_{b}}) - 2 ϕ (u_{i_{a}}, u_{i_{b}}) + d (v_{j_{a}}, v_{j_{b}}) . \end{matrix}$

3. A tight lower bound for $r n (T 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 for achieving the lower bound.

Theorem 3.1. Let

T

be a tree of order

m

and diameter

d \geq 2

. Denote

ε = ε (T)

. Then

\begin{matrix} (6) & r n (T K_{n}) \geq (m n - 1) (d + ε) - 2 n L (T) . \end{matrix}

Proof. It is enough to prove that any radio labelling of $T K_{n}$ has no span less than that of the right-hand side of (6). Suppose $f$ is any radio labelling of $T K_{n}$ which induces an ordering ${\vec{V}}_{f} = (w_{0}, w_{1}, \dots, w_{m n - 1})$ such that $0 = f (w_{0}) < f (w_{1}) < \dots < f (w_{m n - 1})$ . Denote $d i a m (T K_{n}) = d^{'}$ . By the definition of a radio labelling, $f (w_{t + 1}) - f (w_{t}) \geq d^{'} + 1 - d (w_{t}, w_{t + 1})$ for $0 \leq t \leq m n - 2$ . Since $d^{'} = d + 1$ by Observation 2.4, we have $f (w_{t + 1}) - f (w_{t}) \geq d + 2 - d (w_{t}, w_{t + 1})$ for $0 \leq t \leq m n - 2$ . Summing up these $m n - 1$ inequalities, we obtain $\begin{matrix} (7) & s p a n (f) = f (w_{m n - 1}) \geq (m n - 1) (d + 2) - \sum_{t = 0}^{m n - 2} d (w_{t}, w_{t + 1}) . \end{matrix}$

Case 1. $| W (T) | = 1$ . In this case, $δ (u_{i_{t}}, u_{i_{t + 1}}) = 0$ by the definition of $δ$ , $ϕ (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 m n - 2$ . Hence, using (5), we obtain $\begin{aligned} \sum_{t = 0}^{m n - 2} d (w_{t}, w_{t + 1}) = & \sum_{t = 0}^{m n - 2} [L (u_{i_{t}}) + L (u_{i_{t + 1}}) - 2 ϕ (u_{i_{t}}, u_{i_{t + 1}}) + d (v_{j_{t}}, v_{j_{t + 1}})] \\ \leq & \sum_{t = 0}^{m n - 2} [L (u_{i_{t}}) + L (u_{i_{t + 1}}) + d (v_{j_{t}}, v_{j_{t + 1}})] \\ \leq & 2 n \sum_{i = 0}^{m - 1} L (u_{i}) + (m n - 1) - L (u_{i_{0}}) - L (u_{i_{m n - 1}}) \\ \leq & 2 n L (T) + m n - 1. \end{aligned}$ Substituting this into (7), we have $s p a n (f) \geq (m n - 1) (d + 1) - 2 n L (T)$ .

Case 2. $| W (T) | = 2$ . In this case, $0 \leq δ (u_{i_{t}}, u_{i_{t + 1}}) \leq 1$ , $ϕ (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 m n - 2$ . Hence, using (5), we obtain $\begin{aligned} \sum_{t = 0}^{m n - 2} d (w_{t}, w_{t + 1}) = & \sum_{t = 0}^{m n - 2} [L (u_{i_{t}}) + L (u_{i_{t + 1}}) + δ (u_{i_{t}}, u_{i_{t + 1}}) - 2 ϕ (u_{i_{t}}, u_{i_{t + 1}}) \\ + d (v_{j_{t}}, v_{j_{t + 1}})] \\ \leq & \sum_{t = 0}^{m n - 2} [L (u_{i_{t}}) + L (u_{i_{t + 1}}) + 1 + d (v_{j_{t}}, v_{j_{t + 1}})] \\ \leq & 2 n \sum_{i = 0}^{m - 1} L (u_{i}) + (m n - 1) + (m n - 1) - L (u_{i_{0}}) - L (u_{i_{m n - 1}}) \\ \leq & 2 n L (T) + 2 (m n - 1) . \end{aligned}$ Substituting this into (7), we have $s p a n (f) \geq (m n - 1) d - 2 n L (T)$ .

Theorem 3.2. Let

T

be a tree of order

m

and diameter

d \geq 2

. Denote

ε = ε (T)

. Then

\begin{matrix} (8) & r n (T K_{n}) = (m n - 1) (d + ε) - 2 n L (T), \end{matrix}

if and only if there exists an ordering

w_{0}, w_{1}, \dots, w_{m n - 1}

V (T K_{n})

such that the following hold:

(a) $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0$ ;

(b) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for all $0 \leq t \leq m n - 2$ ;

(c) for $w_{a} = (u_{i_{a}}, v_{j_{a}}), w_{b} = (u_{i_{b}}, v_{j_{b}}) (0 \leq a < b \leq m n - 1)$ , the distance between any two vertices $u_{i_{a}}$ and $u_{i_{b}}$ satisfies

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

Moreover, under these conditions (a)-(c), the mapping $f$ defined by $\begin{matrix} (10) & f (w_{0}) = 0, \end{matrix}$ $\begin{matrix} (11) & f (w_{t + 1}) = f (w_{t}) + d + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}}), 0 \leq t \leq m n - 2, \end{matrix}$ is an optimal radio labelling of $T K_{n}$ .

Proof. Necessity. Suppose that (8) holds. Note that (8) holds if equality hold in (1) and everywhere in the proof of Theorem 3.1. Again observe that if the equality holds everywhere in the proof of Theorem 3.1 then an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T K_{n})$ induced by $f$ satisfies the followings: (1) $L (u_{i_{0}}) = L (u_{i_{m n - 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 m n - 2$ , (3) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for all $0 \leq t \leq m n - 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^{'} + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}}) - 1 = f (w_{t}) + d + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}})$ for $0 \leq t \leq m n - 2$ , where $d^{'} = d i a m (T K_{n})$ . Summing this last equality for $w_{a}$ to $w_{b} (0 \leq a < b \leq m n - 1)$ , we obtain $f (w_{b}) - f (w_{a}) = \sum_{t = a}^{b - 1} [d + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}})] .$

Since $f$ is a radio labelling of $T K_{n}$ , we have $f (w_{b}) - f (w_{a}) \geq d^{'} + 1 - d (w_{a}, w_{b}) = d + 2 - d (w_{a}, w_{b})$ . Also note that $d (w_{a}, w_{b}) = d (u_{i_{a}}, u_{i_{b}}) + 1$ by (5). Substituting these into the above equation, we obtain $d (u_{i_{a}}, u_{i_{b}}) \geq \sum_{t = a}^{b - 1} [L (u_{i_{t}}) + L (u_{i_{t + 1}}) - (d + ε)] + (d + 1) .$

Sufficiency. Suppose there exists an ordering ( $w_{0}$ , $w_{1}$ , $\dots$ , $w_{m n - 1}$ ) of $V (T 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 K_{n}$ and the span of $f$ is the right-hand side of (8). Denote $d i a m (T K_{n}) = d^{'}$ . Let $w_{a}$ and $w_{b} (0 \leq a < b \leq m n - 1)$ be two arbitrary vertices. $\begin{aligned} f (w_{b}) - f (w_{a}) = & \sum_{t = a}^{b - 1} (f (w_{t + 1}) - f (w_{t})), \\ = & \sum_{t = a}^{b - 1} (d + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}})), \\ = & d + 1 - d (u_{i_{a}}, u_{i_{b}}), \\ = & d + 2 - (d (u_{i_{a}}, u_{i_{b}}) + 1), \\ = & d^{'} + 1 - d (w_{a}, w_{b}) . \end{aligned}$ The span of $f$ is $\begin{aligned} s p a n (f) = & f (w_{m n - 1}) - f (w_{0}), \\ = & \sum_{t = 0}^{m n - 2} (f (w_{t + 1}) - f (w_{t})), \\ = & \sum_{t = 0}^{m n - 2} (d + ε - L (u_{i_{t}}) - L (u_{i_{t + 1}})), \\ = & (m n - 1) (d + ε) - 2 \sum_{t = 0}^{m n - 1} L (u_{i_{t}}) + L (u_{i_{0}}) + L (u_{i_{m n - 1}}), \\ = & (m n - 1) (d + ε) - 2 n L (T) . \end{aligned}$

Theorem 3.3. Let

T

be a tree of order

m

and diameter

d \geq 2

. Denote

ε = ε (T)

. Then

\begin{matrix} (12) & r n (T K_{n}) = (m n - 1) (d + ε) - 2 n L (T), \end{matrix}

if and only if there exists an ordering

w_{0}, w_{1}, \dots, w_{m n - 1}

V (T K_{n})

with

w_{t} = (u_{i_{t}}, v_{j_{t}}), 0 \leq t \leq m n - 1

such that the following all hold:

(a) $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0$ ;

(b) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for $0 \leq t \leq m n - 2$ ;

(c) $u_{i_{t}}$ and $u_{i_{t + 1}}$ are in different branches when $| W (T) | = 1$ and in opposite branches when $| W (T) | = 2$ for $0 \leq t \leq m n - 2$ ;

(d) $L (u_{i_{t}}) \leq (d + 1) / 2$ when $| W (T) | = 1$ and $L (u_{i_{t}}) \leq (d - 1) / 2$ when $| W (T) | = 2$ for all $0 \leq t \leq m n - 1$ ;

(e) for any $w_{a} = (u_{i_{a}}, v_{j_{a}}), w_{b} = (u_{i_{b}}, v_{j_{b}}) (0 \leq a < b \leq m n - 1)$ such that $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch of $T$ , $u_{i_{a}}$ and $u_{i_{b}}$ satisfy $\begin{matrix} (13) & ϕ (u_{i_{a}}, u_{i_{b}}) \leq (\frac{b - a - 1}{2}) (d + ε) - \sum_{t = a + 1}^{b - 1} L (u_{i_{t}}) - (\frac{1 - ε}{2}) . \end{matrix}$

Proof. Necessity. Suppose (12) holds. Then there exists an ordering ( $w_{0}$ , $w_{1}$ , $\dots$ , $w_{m n - 1}$ ) of $T K_{n}$ such that the conditions (a)-(c) of Theorem 3.2 holds. Hence the conditions (a) and (b) are satisfied. Taking $a = t$ and $b = t + 1$ in (9), we obtain $d (w_{t}, w_{t + 1}) = d (u_{i_{t}}, u_{i_{t + 1}}) + d (v_{j_{t}}, v_{j_{t + 1}}) = L (u_{i_{t}}) + L (u_{i_{t + 1}}) + 1 - ε + 1$ . Hence we have $d (u_{i_{t}}, u_{i_{t + 1}}) = L (u_{i_{t}}) + L (u_{i_{t + 1}}) + 1 - ε$ for all $0 \leq t \leq m n - 2$ as $0 \leq d (u_{i_{t}}, u_{i_{t + 1}}) \leq L (u_{i_{t}}) + L (u_{i_{t + 1}}) + 1 - ε$ 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 m n - 2$ . Hence the condition (c) is satisfied. Since $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0$ , it is clear that $L (u_{i_{t}}) < (d + 1) / 2$ for $t = 0, m n - 1$ . For $1 \leq t \leq m n - 2$ , considering $u_{i_{t - 1}}$ and $u_{i_{t + 1}}$ in (9) and using (5), we obtain $2 L (u_{i_{t}}) \leq (d + ε) - (1 - ε) + δ (u_{i_{t - 1}}, u_{i_{t + 1}}) - 2 ϕ (u_{i_{t - 1}}, u_{i_{t + 1}}) .$

In above equation, observe that when $| W (T) | = 1$ then $δ (u_{i_{t - 1}}, u_{i_{t + 1}}) = 0$ by the definition of $δ$ 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 $δ (u_{i_{t - 1}}, u_{i_{t + 1}}) = 0$ . Thus we have $2 L (u_{i_{t}}) \leq d + 2 ε - 1.$

Hence, the condition (d) is satisfied. To prove (e), let $w_{a} = (u_{i_{a}}, v_{j_{a}})$ and $w_{b} = (u_{i_{b}}, v_{j_{b}}) (0 \leq a < b \leq m n - 1)$ be such that $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch of $T$ . Then $δ (u_{i_{a}}, u_{i_{b}}) = 0$ . Using (5) in (9), (13) can be obtained easily from (9).

Sufficiency. Suppose there exists an ordering $(w_{0}, w_{1}, \dots, w_{m n - 1})$ of $V (T K_{n})$ such that conditions (a)-(e) hold. To prove (12) holds, we show that an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ satisfies the conditions (a)-(c) of Theorem 3.2. Since the conditions (a) and (b) are identical with the conditions (a) and (b) of Theorem 3.2, we need to prove the condition (9) only. Denote the right-hand side of (9) by $S_{a, b}$ . Let $w_{a} = (u_{i_{a}}, v_{j_{a}}), w_{b} = (u_{i_{b}}, v_{j_{b}}) (0 \leq a < b \leq m n - 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 + ε) + (1 - ε)$ . If $| W (T) | = 1$ , then note that $L (u_{i_{t}}) \leq (d + 1) / 2$ for all $0 \leq t \leq m n - 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 m n - 1$ and hence $S_{a, b} \leq L (u_{i_{a}}) + L (u_{i_{b}}) + 2 (b - a - 1) ((d - 1) / 2) - (b - a - 1) d + 1 = L (u_{i_{a}}) + L (u_{i_{b}}) + 1 - (b - a - a)$ $\leq L (u_{i_{a}}) + L (u_{i_{b}}) = d (u_{i_{a}}, u_{i_{b}})$ . If $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch, then (9) can be obtained easily using (13). This completes the proof.

Theorem 3.4. Let

T

be a tree of order

m

and diameter

d \geq 2

. Denote

ε = ε (T)

. Then

\begin{matrix} (14) & r n (T K_{n}) = (m n - 1) (d + ε) - 2 n L (T), \end{matrix}

if there exists an ordering

w_{0}, w_{1}, \dots, w_{m n - 1}

V (T K_{n})

such that

(a) $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0$ ,

(b) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for all $0 \leq t \leq m n - 2$ ,

(c) $u_{i_{t}}$ and $u_{i_{t + 1}}$ are in different branches when $| W (T) | = 1$ and in opposite branches when $| W (T) | = 2$ for all $0 \leq t \leq m n - 2$ ,

and one of the following holds:

(d) $min {d (u_{i_{t}}, u_{i_{t + 1}}), d (u_{i_{t + 1}}, u_{i_{t + 2}})} \leq (d + 1 - ε) / 2$ for all $0 \leq t \leq m n - 3$ ;

(e) $d (u_{i_{t}}, u_{i_{t + 1}}) \leq (d + 1 + ε) / 2$ for all $0 \leq t \leq m n - 2$ ;

(f) for all $0 \leq t \leq m n - 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 m n - 1)$ such that $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch of $T$ then $b - a \geq d$ .

Proof. We show that if (a)-(c) and one of (d)-(f) holds for an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ such that $w_{t} = (u_{i_{t}}, v_{j_{t}}), 0 \leq t \leq m n - 1$ , then (a)-(e) of Theorem 3.3 are satisfied. Since the conditions (a)-(c) are identical in both Theorems 3.3 and 3.4, we need to verify the conditions (d) and (e) of Theorem 3.3 only. Denote the right-hand side of (13) by $P_{a, b}$ . We consider the following two cases.

Case 1. $| W (T) | = 1$ . In this case, recall that $ε = 1$ and $δ (u_{i_{t}}, u_{i_{t + 1}}) = 0$ for all $0 \leq t \leq m n - 2$ by the definition of $δ$ .

Subcase 1.1. Suppose (a)-(d) hold. It is clear that $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0 \leq (d + 1) / 2$ and for $1 \leq t \leq m n - 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 m n - 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 ϕ (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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ . Assume $b - a = 2$ . Then either $L (u_{i_{a}}) + L (u_{i_{a + 1}}) \leq d / 2$ or $L (u_{i_{a + 1}}) + L (u_{i_{a + 2}}) \leq d / 2$ . Without loss of generality, we may assume that $L (u_{i_{a}}) + L (u_{i_{a + 1}}) \leq d / 2$ . Then $L (u_{i_{a + 1}}) \leq d / 2 - L (u_{i_{a}})$ . Hence, $P_{a, b} = (d + 1) / 2 - L (u_{i_{a + 1}}) \geq (d + 1) / 2 - d / 2 + L (u_{i_{a}}) = L (u_{i_{a}}) + (1 / 2) \geq ϕ (u_{i_{a}}, u_{i_{b}})$ .

Subcase 1.2. Suppose (a)-(c) and (e) hold. Note that $L (u_{i_{0}}) = L (u_{i_{m n - 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 m n - 1$ , we obtain $L (u_{i_{t}}) \leq (d + 1) / 2$ for all $0 \leq t \leq m n - 1$ .

Let $w_{a} = (u_{i_{a}}, v_{j_{a}})$ and $w_{b} = (u_{i_{b}}, v_{j_{b}}), 0 \leq a < b \leq m n - 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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ .

Subcase 1.3. Suppose (a)-(c) and (f) hold. Assume $d$ is even. Then $L (u_{i_{t}}) \leq d / 2$ for all $0 \leq t \leq m n - 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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ .

Case 2. $| W (T) | = 2$ . In this case, recall that $ε = 0$ and $δ (u_{i_{t}}, u_{i_{t + 1}}) = 1$ for all $0 \leq t \leq m n - 1$ by the definition of the ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T K_{n})$ .

Subcase 2.1. Suppose (a)-(d) hold. It is clear that $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = 0 \leq (d - 1) / 2$ and for $1 \leq t \leq m n - 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 m n - 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 / 2 - (d - 1) - 1 / 2 = (d + 1) / 2 \geq ϕ (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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ . Assume $b - a = 2$ . Then either $L (u_{i_{a}}) + L (u_{i_{a + 1}}) \leq (d - 1) / 2$ or $L (u_{i_{a + 1}}) + L (u_{i_{a + 2}}) \leq (d - 1) / 2$ . Without loss of generality, we may assume that $L (u_{i_{a + 1}}) + L (u_{i_{a + 2}}) \leq (d - 1) / 2$ . Then $L (u_{i_{a + 1}}) \leq (d - 1) / 2 - L (u_{i_{a + 2}})$ . Hence, $P_{a, b} = d / 2 - L (u_{i_{a + 1}}) - 1 / 2 \geq d / 2 - ((d - 1) / 2 - L (i_{a + 2})) - 1 / 2 = L (u_{i_{a + 2}}) \geq ϕ (u_{i_{a}}, u_{i_{b}})$ .

Subcase 2.2. Suppose (a)-(c) and (e) hold. Note that $L (u_{i_{0}}) = L (u_{i_{m n - 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 m n - 1$ , we obtain $L (u_{i_{t}}) \leq (d - 1) / 2$ for all $0 \leq t \leq m n - 1$ .

Let $w_{a} = (u_{i_{a}}, v_{j_{a}})$ and $w_{b} = (u_{i_{b}}, v_{j_{b}}), 0 \leq a < b \leq m n - 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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ .

Subcase 2.3. Suppose (a)-(c) and (f) hold. Assume $d$ is even. Then $L (u_{i_{t}}) \leq (d - 2) / 2$ for all $0 \leq t \leq m n - 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 ϕ (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 ϕ (u_{i_{a}}, u_{i_{b}})$ .

4. Radio number of the Cartesian product of a level-wise regular tree and a complete graph

In this section, using the results in Section 3, we determine the radio number of the Cartesian product of a level-wise regular tree and a complete graph.

It is well known that the center of tree $T$ consists of one vertex $r$ or two adjacent vertices $r, r^{'}$ depending on $d i a m (T)$ is even or odd. We view a tree $T$ rooted at $r$ or at both $r, r^{'}$ respectively. Halász and Tuza [9] defined a level-wise regular tree to be a tree $T$ in which all vertices at distance $i$ from root $r$ or ${r, r^{'}}$ have the same degree, say, $d_{i}$ for $0 \leq i \leq h$ , where $h$ (the largest distance from a vertex to the root) is the height of tree $T$ . Note that a level-wise regular tree is determined by its center(s) and $(d_{0}, d_{1}, \dots, d_{h - 1})$ . Denote the level-wise regular tree by $T^{z} = T_{d_{0}, d_{1}, \dots, d_{h - 1}}^{z}$ , where $z$ denotes the number of roots of the level-wise regular tree. A star $K_{1, q}$ is a tree consisting of $q$ leaves and another vertex joined to all leaves by edges. A double star $D_{q}$ is a graph obtained by joining the center vertices of two copies of star graph $K_{1, q}$ by an edge. A banana tree $B_{q, k}$ is a graph constructed by connecting a single leaf from $q$ distinct copies of a star $K_{1, k}$ with a single vertex that is distinct from all the vertices of the star graphs. Note that $K_{1, q}$ , $D_{q}$ and $B_{q, k}$ are level-wise regular trees $T_{q}^{1}$ , $T_{q + 1}^{2}$ and $T_{q, 2, k}^{1}$ , respectively.

Theirem 3.1. Let

h \geq 1

and

d_{i}, n \geq 3

for

0 \leq i \leq h - 1

be integers. Denote

ε = ε (T^{z})

. Then

r n (T^{z} K_{n})

\begin{matrix} (15) & {\begin{cases} [(\sum_{i = 1}^{h - 1} (2 h - 2 i - 1) (\prod_{1 \leq j \leq i} (d_{j} - 1))) + 2 h - 1] n d_{0} + (2 h + 1) (n - 1), & if z = 1, \\ [(\sum_{i = 0}^{h - 1} (2 h - 2 i - 1) (\prod_{0 \leq j \leq i} (d_{j} - 1))) + 2 h + 1] 2 n - 2 h - 1, & if z = 2 . \end{cases} \end{matrix}

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} \sum_{i = 1}^{h - 1} (\prod_{1 \leq j \leq i} (d_{j} - 1)), & if z = 1, \\ 2 + 2 \sum_{i = 0}^{h - 1} (\prod_{0 \leq j \leq i} (d_{j} - 1)), & if z = 2, \end{cases}$

$L (T^{z}) = {\begin{cases} d_{0} + d_{0} \sum_{i = 1}^{h - 1} (i + 1) (\prod_{1 \leq j \leq i} (d_{j} - 1)), & if z = 1, \\ 2 \sum_{i = 0}^{h - 1} (i + 1) (\prod_{0 \leq j \leq i} (d_{j} - 1)), & if z = 2, \end{cases}$

$d = {\begin{cases} 2 h, & if z = 1, \\ 2 h + 1, & if z = 2 . \end{cases}$ Substituting the above into (6), we obtain the right-hand side of (15) as a lower bound for $r n (T^{z} K_{n})$ . We now prove that this lower bound is tight by giving an ordering of $V (T^{z} K_{n})$ which satisfies the conditions in Theorem 3.2. For this purpose, denote $V (K_{n}) = {v_{0}, v_{1}, \dots, v_{n - 1}}$ and $V (T^{z}) = {u_{0}, u_{1}, \dots, u_{m - 1}}$ such that the ordering $u_{0}, u_{1}, \dots, 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}, \dots, 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}, \dots, r_{i, d_{1} - 1}$ . Inductively, denote the $d_{l} - 1$ children of $r_{i_{1}, i_{2}, \dots, i_{l}} (0 \leq i_{1} \leq d_{0} - 1, 0 \leq i_{2} \leq d_{1} - 1, \dots, 0 \leq i_{l} \leq d_{l - 1} - 1)$ by $r_{i_{1}, i_{2}, \dots, i_{l}, i_{l + 1}}$ , where $0 \leq i_{l + 1} \leq d_{l} - 1$ . Continue this process until all the vertices of $T^{1}$ get indexed. Now obtain an ordering $u_{0}, u_{1}, \dots, 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}, \dots, i_{l}}$ , where $j = 1 + i_{1} + i_{2} d_{0} + \dots + i_{l} d_{0} (d_{1} - 1) \dots (d_{l} - 1) + \sum_{l + 1 \leq t \leq h} d_{0} (d_{1} - 1) \dots (d_{t} - 1)$ .

Case-2. $z = 2$ .

In this case, let $r$ and $r^{'}$ be two centers of $T^{2}$ . Denote $d_{0} - 1$ children of $r$ and $r^{'}$ by $r_{0}, r_{1}, \dots, r_{d_{0} - 2}$ and $r_{0}^{'}, r_{1}^{'}, \dots, r_{d_{0} - 2}^{'}$ , respectively. For $0 \leq i \leq d_{0} - 2$ , denote $d_{1} - 1$ children of $r_{i}$ and $r_{i}^{'}$ by $r_{i, 0}, r_{i, 1}, \dots, r_{i, d_{1} - 1}$ and $r_{i, 0}^{'}, r_{i, 1}^{'}, \dots, r_{i, d_{1} - 1}^{'}$ , respectively. Inductively, denote the $d_{l} - 1$ children of $r_{i_{1}, i_{2}, \dots, i_{l}}$ and $r_{i_{1}, i_{2}, \dots, i_{l}}^{'}$ , where $0 \leq i_{1} \leq d_{0} - 2, 0 \leq i_{2} \leq d_{1} - 1, \dots, 0 \leq i_{l} \leq d_{l - 1} - 1$ by $r_{i_{1}, i_{2}, \dots, i_{l}, i_{l + 1}}$ and $r_{i_{1}, i_{2}, \dots, i_{l}, i_{l + 1}}^{'}$ respectively, where $0 \leq i_{l + 1} \leq d_{l} - 1$ . Continue this process until all the vertices of $T^{2}$ are indexed. Rename $x_{j} := r_{i_{1}, i_{2}, \dots, i_{l}} and x_{j}^{'} := r_{i_{1}, i_{2}, \dots, i_{l}}^{'}$ , where $j = 1 + i_{1} + i_{2} (d_{0} - 1) + \dots + i_{l} (d_{0} - 1) (d_{1} - 1) \dots (d_{l} - 1) + \sum_{l + 1 \leq t \leq h} (d_{0} - 1) (d_{1} - 1) \dots (d_{t} - 1)$ . Now obtain an ordering $u_{0}, u_{1}, \dots, u_{m - 1}$ as follows: Set $u_{0} := r, u_{m - 1} := r^{'}$ and for $1 \leq t \leq m - 2$ , set $u_{t} := {\begin{cases} x_{t / 2}, & if t \equiv 0 (mod 2), \\ x_{(t + 1) / 2}^{'}, & if t \equiv 1 (mod 2) . \end{cases}$

We now consider the following two cases to give an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T K_{n}) = {(u_{i}, v_{j}) : i = 0, 1, \dots, m - 1, j = 0, 1, \dots, n - 1}$ .

Case 1. $| W (T) | = 1$ .

We consider the following two subcases to define an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T^{1} K_{n})$ .

Subcase 1. $| V (T^{1}) | \leq | V (K_{n}) |$ .

In this case, for $0 \leq t \leq m n - 1$ , define $w_{t} := (u_{i}, v_{j})$ , where $i \in {0, 1, \dots, m - 1} j \in {0, 1, \dots, n - 1}$ and $t := {\begin{cases} m (j - i) + i & if j \geq i and j - i \neq n - 1, \\ m (n + j - i) + i & if j < i and i - j \neq 1, \\ m (n + j - i) + i - 1 & if j < i and i - j = 1, \\ m n - 1 & if j - i = n - 1 . \end{cases}$

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

In this case, for $x l c m (m, n) \leq t \leq (x + 1) l c m (m, n) - 1$ , where $0 \leq x \leq gcd (m, n) - 1$ , set $α_{t} := {\begin{cases} (u_{i}, v_{j + x}), & if t \equiv i (mod m), t \equiv j (mod n) and 0 \leq j \leq n - (x + 1), \\ (u_{i}, v_{j + x - n}), & if t \equiv i (mod m), t \equiv j (mod n) and n - x \leq j \leq n - 1 . \end{cases}$

Define an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T^{1} K_{n})$ as follows: For $0 \leq t \leq m n - 1$ , set $w_{t} := {\begin{cases} α_{t}, & if 0 \leq t \leq m n - m - 1, \\ α_{t + 1}, & if m n - m \leq t \leq m n - 2, \\ α_{m n - m}, & if t = m n - 1 . \end{cases}$

Then, for above defined ordering, it is clear that (a) $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = L (u_{0}) = 0$ , (b) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for $0 \leq t \leq m n - 2$ , (c) $u_{i_{t}}$ and $u_{i_{t + 1}}$ are in different branches for $0 \leq t \leq m n - 2$ , and (d) $L (u_{i_{t}}) \leq d / 2$ for all $0 \leq t \leq m n - 1$ . Hence the conditions (a)-(d) in Theorem 3.3 are satisfied. We now show that the condition (e) of Theorem 3.3 holds.

The above defined ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T^{1} 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 m n - 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$ , $ε = 1$ and $L (u_{t}) \leq d / 2$ for all $0 \leq t \leq m n - 1$ . Observe that for $w_{a} = (u_{i_{a}}, v_{j_{a})}$ and $w_{b} = (u_{i_{b}}, v_{j_{b}})$ such that $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch of $T^{2}$ , there are two possibilities: (1) $i_{a} \neq i_{b}$ (2) $i_{a} = i_{b}$ . In case (1), we have $b - a \geq α d_{0}$ , where $α \geq ϕ (u_{i_{a}}, u_{i_{b}})$ . Hence, $P_{a, b} = ((b - a - 1) / 2) (d + 1) - \sum_{t = a + 1}^{b - 1} L (u_{i_{t}}) \geq ((b - a - 1) / 2) (d + 1)$ $- \sum_{t = a + 1}^{b - 1} (d / 2) = ((b - a - 1) / 2) = α (d_{0} - 1) / 2 \geq ϕ (u_{i_{a}}, u_{i_{b}})$ . In case (2), note that $b - a \geq m \geq d + 1$ . Hence, $P_{a, b} = ((b - a - 1) / 2) (d + 1) - \sum_{t = a + 1}^{b - 1} L (u_{i_{t}}) \geq ((b - a - 1) / 2) (d + 1) - \sum_{t = a + 1}^{b - 1} (d / 2) = ((b - a - 1) / 2)$ $= d / 2 \geq ϕ (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}, \dots, w_{m n - 1}$ of $V (T^{2} K_{n})$ .

Subcase 1. $| V (T) | \leq | V (K_{n}) |$ .

In this case, for $0 \leq t \leq m n - 1$ , define $w_{t} := (u_{i}, v_{j})$ , where $i \in {0, 1, \dots, m - 1}, j \in {0, 1, \dots, n - 1}$ and $t := {\begin{cases} m (j - i) + i, & if j \geq i, \\ m (n + j - i) + i, & if j < i . \end{cases}$

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

In this case, define an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (T^{2} K_{n})$ as follows: For $x l c m (m, n) \leq t \leq (x + 1) l c m (m, n) - 1$ , where $0 \leq x \leq gcd (m, n) - 1$ , set $w_{t} := {\begin{cases} (u_{i}, v_{j + x}), & if t \equiv i (mod m), t \equiv j (mod n) and 0 \leq j \leq n - (x + 1), \\ (u_{i}, v_{j + x - n}), & if t \equiv i (mod m), t \equiv j (mod n) and n - x \leq j \leq n - 1, \end{cases}$

Then, for above defined ordering, it is clear that (a) $L (u_{i_{0}}) = L (u_{i_{m n - 1}}) = L (u_{0}) = 0$ , (b) $v_{j_{t}}$ and $v_{j_{t + 1}}$ are distinct for $0 \leq t \leq m n - 2$ , (c) $u_{i_{t}}$ and $u_{i_{t + 1}}$ are in different branches for $0 \leq t \leq m n - 2$ , and (d) $L (u_{i_{t}}) \leq (d - 1) / 2$ for all $0 \leq t \leq m n - 1$ . Hence the conditions (a)-(d) of Theorem 3.3 are satisfied. Now we prove that the condition (e) of Theorem 3.3 holds.

Claim 2. The above defined ordering

w_{0}, w_{1}, \dots, w_{m n - 1}

V (T^{2} 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 m n - 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$ , $ε = 0$ and $L (u_{t}) \leq (d - 1) / 2$ for all $0 \leq t \leq m n - 1$ . Observe that for $w_{a} = (u_{i_{a}}, v_{j_{a}})$ and $w_{b} = (u_{i_{b}}, v_{j_{b}})$ such that $u_{i_{a}}$ and $u_{i_{b}}$ are in the same branch of $T^{2}$ , there are two possibilities: (1) $i_{a} \neq i_{b}$ , (2) $i_{a} = i_{b}$ . In case (1), we have $b - a \geq α (d_{0} - 1)$ , where $α \geq ϕ (u_{i_{a}}, u_{i_{b}})$ . Hence, $P_{a, b} = ((b - a - 1) / 2) d - \sum_{t = a + 1}^{b - 1} L (u_{i_{t}}) - 1 / 2 \geq ((b - a - 1) / 2) d - \sum_{t = a + 1}^{b - 1} ((d - 1) / 2) - 1 / 2$ $= (b - a - 2) / 2 = α (d_{0} - 1) / 2 \geq ϕ (u_{i_{a}}, u_{i_{b}})$ . In case (2), note that $b - a \geq m \geq d + 1$ . Hence, $P_{a, b} = ((b - a - 1) / 2) d$ $- \sum_{t = a + 1}^{b - 1} L (u_{i_{t}}) - 1 / 2 \geq ((b - a - 1) / 2) d - \sum_{t = a + 1}^{b - 1} ((d - 1) / 2) - 1 / 2 = (b - a - 2) / 2 = α (d - 1) / 2 \geq ϕ (u_{i_{a}}, u_{i_{b}})$ .

Corollary 4.2. Let

q \geq 3

and

n \geq 4

be integers. Then

r n (K_{1, q} K_{n}) = (q + 3) n - 3.

Corollary 4.3. Let

q \geq 2

and

n \geq 4

be integers. Then

r n (D_{q} K_{n}) = 2 n (q + 3) - 3.

Corollary 4.4. Let

k, n \geq 4

and

q \geq 5

be integers. Then

r n (B_{q, k} K_{n}) = q n (k + 6) + 7 (n - 1) .

Exmple 4.5 . In Table 1, a vertex ordering

O (V (K_{1, 6} K_{7})) := w_{0}, w_{1}, \dots, w_{48}

and an optimal radio labelling of

K_{1, 6} K_{7}

are shown.

Table 1 $r n (K_{1, 6} 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} \to 0$	$w_{7} \to 9$	$w_{14} \to 18$	$w_{21} \to 27$	$w_{28} \to 36$	$w_{35} \to 45$	$w_{48} \to 60$
$u_{1}$	$w_{42} \to 53$	$w_{1} \to 2$	$w_{8} \to 11$	$w_{15} \to 20$	$w_{22} \to 29$	$w_{29} \to 38$	$w_{36} \to 47$
$u_{2}$	$w_{37} \to 48$	$w_{43} \to 54$	$w_{2} \to 3$	$w_{9} \to 12$	$w_{16} \to 21$	$w_{23} \to 30$	$w_{30} \to 39$
$u_{3}$	$w_{31} \to 40$	$w_{38} \to 49$	$w_{44} \to 55$	$w_{3} \to 4$	$w_{10} \to 13$	$w_{17} \to 22$	$w_{24} \to 31$
$u_{4}$	$w_{25} \to 32$	$w_{32} \to 41$	$w_{39} \to 50$	$w_{45} \to 56$	$w_{4} \to 5$	$w_{11} \to 14$	$w_{18} \to 23$
$u_{5}$	$w_{19} \to 24$	$w_{26} \to 33$	$w_{33} \to 42$	$w_{40} \to 51$	$w_{46} \to 57$	$w_{5} \to 6$	$w_{12} \to 15$
$u_{6}$	$w_{13} \to 16$	$w_{20} \to 25$	$w_{27} \to 34$	$w_{34} \to 43$	$w_{41} \to 52$	$w_{47} \to 58$	$w_{6} \to 7$

Example 4.6. In Table 2, a vertex ordering

O (V (D_{5} K_{7})) := w_{0}, w_{1}, \dots, w_{83}

and an optimal radio labelling of

D_{5} K_{7}

are shown.

Table 2 $r n (D_{5} 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} \to 0$	$w_{36} \to 48$	$w_{72} \to 96$	$w_{24} \to 32$	$w_{60} \to 80$	$w_{12} \to 16$	$w_{48} \to 64$
$u_{1}$	$w_{49} \to 66$	$w_{1} \to 2$	$w_{37} \to 50$	$w_{73} \to 98$	$w_{25} \to 34$	$w_{61} \to 82$	$w_{13} \to 18$
$u_{2}$	$w_{14} \to 19$	$w_{50} \to 67$	$w_{2} \to 3$	$w_{38} \to 51$	$w_{74} \to 99$	$w_{26} \to 35$	$w_{62} \to 83$
$u_{3}$	$w_{63} \to 84$	$w_{15} \to 20$	$w_{51} \to 68$	$w_{3} \to 4$	$w_{39} \to 52$	$w_{75} \to 100$	$w_{27} \to 36$
$u_{4}$	$w_{28} \to 37$	$w_{64} \to 85$	$w_{16} \to 21$	$w_{52} \to 69$	$w_{4} \to 5$	$w_{40} \to 53$	$w_{76} \to 101$
$u_{5}$	$w_{77} \to 102$	$w_{29} \to 38$	$w_{65} \to 86$	$w_{17} \to 22$	$w_{53} \to 70$	$w_{5} \to 6$	$w_{41} \to 54$
$u_{6}$	$w_{42} \to 55$	$w_{78} \to 103$	$w_{30} \to 39$	$w_{66} \to 87$	$w_{18} \to 23$	$w_{54} \to 71$	$w_{6} \to 7$
$u_{7}$	$w_{7} \to 8$	$w_{43} \to 56$	$w_{79} \to 104$	$w_{31} \to 40$	$w_{67} \to 88$	$w_{19} \to 24$	$w_{55} \to 72$
$u_{8}$	$w_{56} \to 73$	$w_{8} \to 9$	$w_{44} \to 57$	$w_{80} \to 105$	$w_{32} \to 41$	$w_{68} \to 89$	$w_{20} \to 25$
$u_{9}$	$w_{21} \to 26$	$w_{57} \to 74$	$w_{9} \to 10$	$w_{45} \to 58$	$w_{81} \to 106$	$w_{33} \to 42$	$w_{69} \to 90$
$u_{10}$	$w_{70} \to 91$	$w_{22} \to 27$	$w_{58} \to 75$	$w_{10} \to 11$	$w_{46} \to 59$	$w_{82} \to 107$	$w_{34} \to 43$
$u_{11}$	$w_{35} \to 45$	$w_{71} \to 93$	$w_{23} \to 29$	$w_{59} \to 77$	$w_{11} \to 13$	$w_{47} \to 61$	$w_{83} \to 109$

5. 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: $\begin{matrix} (16) & r n (P_{m} K_{n}) = {\begin{cases} \frac{m^{2} n - 2 m + 2}{2}, & if m is even, \\ \frac{m^{2} n - 2 m + n + 2}{2}, & if m is odd . \end{cases} \end{matrix}$ This result can be proved using our results. The outline of the proof is as follows: Since a path $P_{m}$ is a tree, we use Theorems 3.1 and 3.2 to prove the result. Note that the diameter $d$ of $P_{m}$ is $m - 1$ . We consider the following two cases.

Case 1. $m$ is even. In this case, the total level of a path $P_{m}$ is given by $L (P_{m}) = m (m - 2) / 2$ . Substituting this into (6), we obtain $r n (P_{m} K_{n}) \geq (m^{2} n - 2 m + 2) / 2$ . Now observe that the ordering of $V (P_{m} K_{n})$ given in [11] satisfies the conditions (a)-(c) in Theorem 3.2 and hence we obtain that the first line in (16) holds.

Case 2. $m$ is odd. In this case, the total level of a path $P_{m}$ is given by $L (P_{m}) = (m^{2} - 1) / 2$ . Substituting this into (6), we obtain $r n (P_{m} K_{n}) \geq (m^{2} n - 2 m + n) / 2$ . Now assume that $r n (P_{m} K_{n}) = (m^{2} n - 2 m + n) / 2$ . Then by Theorem 3.2, there exists an ordering $w_{0}, w_{1}, \dots, w_{m n - 1}$ of $V (P_{m} K_{n})$ such that the conditions (a)-(c) in Theorem 3.2 hold. Since $L (u_{i_{0}}) = L (u_{i_{m n - 1}})$ by (a), observe that there exists a vertex $w_{k} = (u_{i_{k}}, v_{j_{k}})$ such that $L (u_{i_{k}}) = (m - 1) / 2$ and $L (u_{i_{k - 1}}) \neq 0, L (u_{i_{k + 1}}) \neq 0$ . Note that $d (u_{i_{k - 1}}, u_{i_{k + 1}}) = L (u_{i_{k - 1}}) + L (u_{i_{k + 1}}) - 2 ϕ (u_{i_{k - 1}}, u_{i_{k + 1}})$ with $ϕ (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}}) + 2 L (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 ϕ (u_{i_{k - 1}}, u_{i_{k + 1}}) = d (u_{i_{k - 1}}, u_{i_{k + 1}})$ , which is a contradiction. Hence, $r n (P_{m} K_{n}) \geq (m^{2} n - 2 m + n + 2) / 2$ . Now observe that the ordering of $V (P_{m} K_{n})$ given in [11] satisfies the conditions (a)-(c) in Theorem 3.2. Hence we obtain that the second line in (16) holds, and this completes the proof.

Acknowledgement

The authors are grateful to the two anonymous referees for their careful reading of the manuscript and helpful comments. The research of the second author is supported by Research Promotion under Technical Education – STEM research project grant (Project ID: 202122MATH01) of the Government of Gujarat.

Statements and declarations

The authors have no relevant financial or non-financial interests to disclose.

References:

D. Bantva. Further results on the radio number of trees. Electronic Notes in Discrete Mathematics, 63:85–91, 2017. https://doi.org/10.1016/j.endm.2017.11.002.
D. Bantva and D. D.-F. Liu. Optimal radio labellings of block graphs and line graphs of trees. Theoretical Computer Science, 891:90–104, 2021. https://doi.org/10.1016/j.tcs.2021.08.029.
D. Bantva, S. Vaidya, and S. Zhou. Radio number of trees. Discrete Applied Mathematics, 217:110–122, 2017. https://doi.org/10.1016/j.dam.2016.09.019.
K. Benson, M. Porter, and M. Tomova. The radio numbers of all graphs of order n and diameter n – 2. arXiv preprint arXiv:1206.6327, 2012. https://doi.org/10.48550/arXiv.1206.6327.
T. Calamoneri. The l (h, k)-labelling problem: an updated survey and annotated bibliography. The Computer Journal, 54(8):1344–1371, 2011. 10.1093/comjnl/bxr037.
G. Chartrand and D. Erwin. A graph labeling problem suggested by FM channel. Bulletin of the Institute of Combinatorics and Its Applications, 2005.
G. Chartrand, D. Erwin, F. Harary, and P. Zhang. Radio labelings of graphs. Bulletin of the Institute of Combinatorics and its Applications, 33:77–85, 2001.
J. R. Griggs and R. K. Yeh. Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595, 1992. https://doi.org/10.1137/0405048.
V. Halász and Z. Tuza. Distance-constrained labeling of complete trees. Discrete Mathematics, 338(8):1398–1406, 2015. https://doi.org/10.1016/j.disc.2015.02.016.
W. K. Hale. Frequency assignment: theory and applications. Proceedings of the IEEE, 68(12):1497–1514, 1980. 10.1109/PROC.1980.11899.
B. M. Kim, W. Hwang, and B. C. Song. Radio number for the product of a path and a complete graph. Journal of Combinatorial Optimization, 30:139–149, 2015. https://doi.org/10.1007/s10878-013-9639-3.
X. Li, V. Mak, and S. Zhou. Optimal radio labellings of complete m-ary trees. Discrete Applied Mathematics, 158(5):507–515, 2010. https://doi.org/10.1016/j.dam.2009.11.014.
D. D.-F. Liu. Radio number for trees. Discrete Mathematics, 308(7):1153–1164, 2008. https://doi.org/10.1016/j.disc.2007.03.066.
D. D.-F. Liu, L. Saha, and S. Das. Improved lower bounds for the radio number of trees. Theoretical Computer Science, 851:1–13, 2021. https://doi.org/10.1016/j.tcs.2020.05.023.
D. D.-F. Liu and M. Xie. Radio number for square of cycles. Congressus Numerantium, 169:105–125, 2004.
D. D.-F. Liu and M. Xie. Radio number for square paths. Ars Combinatoria, 90:307–319, 2009.
D. D.-F. Liu and X. Zhu. Multilevel distance labelings for paths and cycles. SIAM Journal on Discrete Mathematics, 19(3):610–621, 2005. https://doi.org/10.1137/S0895480102417768.
R. K. Yeh. A survey on labeling graphs with a condition at distance two. Discrete Mathematics, 306(12):1217–1231, 2006. https://doi.org/10.1016/j.disc.2005.11.029.

[1] D. Bantva. Further results on the radio number of trees. Electronic Notes in Discrete Mathematics, 63:85–91, 2017. https://doi.org/10.1016/j.endm.2017.11.002.

[2] D. Bantva and D. D.-F. Liu. Optimal radio labellings of block graphs and line graphs of trees. Theoretical Computer Science, 891:90–104, 2021. https://doi.org/10.1016/j.tcs.2021.08.029.

[3] D. Bantva, S. Vaidya, and S. Zhou. Radio number of trees. Discrete Applied Mathematics, 217:110–122, 2017. https://doi.org/10.1016/j.dam.2016.09.019.

[4] K. Benson, M. Porter, and M. Tomova. The radio numbers of all graphs of order n and diameter n – 2. arXiv preprint arXiv:1206.6327, 2012. https://doi.org/10.48550/arXiv.1206.6327.

[5] T. Calamoneri. The l (h, k)-labelling problem: an updated survey and annotated bibliography. The Computer Journal, 54(8):1344–1371, 2011. 10.1093/comjnl/bxr037.

[6] G. Chartrand and D. Erwin. A graph labeling problem suggested by FM channel. Bulletin of the Institute of Combinatorics and Its Applications, 2005.

[7] G. Chartrand, D. Erwin, F. Harary, and P. Zhang. Radio labelings of graphs. Bulletin of the Institute of Combinatorics and its Applications, 33:77–85, 2001.

[8] J. R. Griggs and R. K. Yeh. Labelling graphs with a condition at distance 2. SIAM Journal on Discrete Mathematics, 5(4):586–595, 1992. https://doi.org/10.1137/0405048.

[9] V. Halász and Z. Tuza. Distance-constrained labeling of complete trees. Discrete Mathematics, 338(8):1398–1406, 2015. https://doi.org/10.1016/j.disc.2015.02.016.

[10] W. K. Hale. Frequency assignment: theory and applications. Proceedings of the IEEE, 68(12):1497–1514, 1980. 10.1109/PROC.1980.11899.

[11] B. M. Kim, W. Hwang, and B. C. Song. Radio number for the product of a path and a complete graph. Journal of Combinatorial Optimization, 30:139–149, 2015. https://doi.org/10.1007/s10878-013-9639-3.

[12] X. Li, V. Mak, and S. Zhou. Optimal radio labellings of complete m-ary trees. Discrete Applied Mathematics, 158(5):507–515, 2010. https://doi.org/10.1016/j.dam.2009.11.014.

[13] D. D.-F. Liu. Radio number for trees. Discrete Mathematics, 308(7):1153–1164, 2008. https://doi.org/10.1016/j.disc.2007.03.066.

[14] D. D.-F. Liu, L. Saha, and S. Das. Improved lower bounds for the radio number of trees. Theoretical Computer Science, 851:1–13, 2021. https://doi.org/10.1016/j.tcs.2020.05.023.

[15] D. D.-F. Liu and M. Xie. Radio number for square of cycles. Congressus Numerantium, 169:105–125, 2004.

[16] D. D.-F. Liu and M. Xie. Radio number for square paths. Ars Combinatoria, 90:307–319, 2009.

[17] D. D.-F. Liu and X. Zhu. Multilevel distance labelings for paths and cycles. SIAM Journal on Discrete Mathematics, 19(3):610–621, 2005. https://doi.org/10.1137/S0895480102417768.

[18] R. K. Yeh. A survey on labeling graphs with a condition at distance two. Discrete Mathematics, 306(12):1217–1231, 2006. https://doi.org/10.1016/j.disc.2005.11.029.

Contents

Congressus Numerantium

Radio number of the cartesian product of a tree and a complete graph

Abstract

1. Introduction

2. Preliminaries

3. A tight lower bound for $r n (T K_{n})$

4. Radio number of the Cartesian product of a level-wise regular tree and a complete graph

5. Concluding remarks

Acknowledgement

Statements and declarations

References:

Information

Guidelines

CP Initiatives

Follow CP

Contents

Congressus Numerantium

Radio number of the cartesian product of a tree and a complete graph

Abstract

1. Introduction

2. Preliminaries

3. A tight lower bound for rn(TKn)

4. Radio number of the Cartesian product of a level-wise regular tree and a complete graph

5. Concluding remarks

Acknowledgement

Statements and declarations

References:

Information

Guidelines

CP Initiatives

Follow CP

3. A tight lower bound for $r n (T K_{n})$