# Radio Numbers of Certainm-Distant Trees

Authors: Srinivasa Rao Kola; Pratima Panigrahi
Journal: Journal of Discrete Mathematics
 (2014)

---

## Abstract

Radio coloring of a graph G with diameter d is an assignment f of positive integers to the vertices of G such that |
f
(
u
)
-
f
(
v
)
|
≥
1
+
d
-
d
(
u
,
v
), where u and v are any two distinct vertices of G and d
(
u
,
v
) is the distance between u and v. The number max {
f
(
u
)
:
u
∈
V
(
G
)
} is called the span of f.  The minimum of spans over all radio colorings of G is called radio number of G, denoted by r
n
(
G
). An m-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V
(
T
)
∖
V
(
P
) is at the most distance m from P. This path P is called a central path. For every tree T, there is an integer m such that T is a m-distant tree. In this paper, we determine the radio number of some m-distant trees for any positive integer m
≥
2, and as a consequence of it, we find the radio number of a class of 1-distant trees (or caterpillars).


---

## Body

## 1. Introduction

Thechannel assignment problem is the problem of assigning frequencies to transmitters in some optimal manner and with no interferences; see Hale [1]. Chartrand et al. [2] introducedradio
k
-colorings of graphs which is a variation of Hale’s channel assignment problem, in which one seeks to assign positive integers to the vertices of a graph G subject to certain constraints involving the distance between the vertices. For any simple connected graph G with diameter d and a positive integer k, 1
≤
k
≤
d, specifically, a radio k-coloring of G is an assignment f of positive integers to the vertices of G such that |
f
(
u
)
-
f
(
v
)
|
≥
1
+
k
-
d
(
u
,
v
), where u and v are any two distinct vertices of G and d
(
u
,
v
) is the distance between u and v. The maximum color (positive integer) assigned by f to some vertex of G is called thespan of f, denoted by r
c
k
(
f
). The minimum of spans of all possible radio k-colorings of G is called the radio k
-chromatic number of G, denoted by r
c
k
(
G
). A radio k-coloring with span r
c
k
(
G
) is called minimal radio k-coloring of G. Radio k-colorings have been studied by many authors; see [3–9].Although the positive integerk can have value in-between 1 and d, the case k
=
d has become a special interest for many authors. Radio d-coloring is simply called radio coloring and radio d-chromatic number is radio number. Here we concentrate on radio number of trees. Kchikech et al. [4] have found the exact value of the radio k-chromatic number of stars K
1
,
n as n
(
k
-
1
)
+
2 and have also given an upper bound for radio k-chromatic number, r
c
k
(
T
), k
≥
2, of an arbitrary non-star-tree T on n vertices as (
n
-
1
)
(
k
-
1
). Liu [5] has given a lower bound for the radio number r
n
(
T
) of an n-vertex tree with diameter d as (
n
-
1
)
(
d
+
1
)
+
1
-
2
w
(
T
), where w
(
T
) is the weight of T defined as w
(
T
)
=
min
⁡
u
∈
V
(
T
)
∑
v
∈
V
(
T
)
‍
d
(
u
,
v
). She also has characterized the trees achieving this bound. In the same paper, Liu considered spiders denoted by S
l
1
,
l
2
,
l
3
,
…
,
l
m, which are trees having a vertex v of degree m
≥
3, and m number of paths of length l
1
,
l
2
,
…
,
l
m whose one end vertex is v and other ends are pendant vertices. She has given a lower bound for the radio number of S
l
1
,
l
2
,
l
3
,
…
,
l
m as ∑
i
=
1
m
‍
l
i
(
l
1
+
l
2
-
l
i
)
+
(
l
1
-
l
2
)
/
2
(
l
1
-
l
2
)
/
2
+
1, where l
1
≥
l
2
≥
⋯
≥
l
m, and has also characterized the spiders achieving this bound. Li et al. [10] have determined the radio number of complete m-ary trees (m
≥
3) with height k (≥2), denoted by T
k
,
m, as (
m
k
+
2
+
m
k
+
1
-
2
k
m
2
+
(
2
k
-
3
)
m
+
1
)
/
(
m
-
1
)
2.In this paper, we determine the radio number of somem-distant trees for any positive integer m
≥
2, and as a consequence of it, we find the radio number of a class of 1-distant trees (orcaterpillars).


## 2. Radio Numbers of Somem-Distant Trees

Recall that anm
-distant tree T is a tree in which there is a path P of maximum length such that every vertex in V
(
T
)
∖
V
(
P
) is at the most distance m from P. This path P is called acentral path. Since we consider the path P as a path of maximum length, the end vertices of P are of degree one vertices in the m-distant tree; that is, if P: a
1
a
2
⋯
a
k is a central path of T, then d
e
g
T
(
a
1
)
=
d
e
g
T
(
a
k
)
=
1. For every tree T, there is an integer m such that T is a m-distant tree. Usually 1-distant trees are known as caterpillars.Before we present the main result of the paper, we give a definition and a lemma below which will be used in the sequel. From the definition of a radio coloringf, one observes that for any two vertices u and v, the quantity |
f
(
u
)
-
f
(
v
)
|
-
{
1
+
d
-
d
(
u
,
v
)
} is an excess for f to achieve the minimum span. In the definition, we give notation for these excesses corresponding to pair of vertices. In the lemma, we show that to get an optimal radio k-coloring, one has to minimize this sum of excesses.Definition 1.
For any radio coloringf of a simple connected graph G on n vertices and an ordering x
1
,
x
2
,
…
,
x
n of vertices of G with f
(
x
i
)
≤
f
(
x
i
+
1
), 1
≤
i
≤
n
-
1, we define ϵ
i (or ϵ
i
f to specify the coloring f) =
{
f
(
x
i
)
-
f
(
x
i
-
1
)
}
-
{
1
+
d
-
d
(
x
i
,
x
i
-
1
)
}, 2
≤
i
≤
n. It is clear from the definition of radio coloring that ϵ
i
≥
0, for all i. With respect to the ordering of vertices of G induced by f, we denote d
(
f
)
=
∑
i
=
2
n
‍
d
(
x
i
,
x
i
-
1
). In other words, every radio coloring f is associated with a unique positive integer d
(
f
) calleddistance sum of f.Example 2.
In this example, we explain Definition1.In Figure1, a radio coloring f of a tree T is given. The labels x
1
,
x
2
,
x
3
,
…
,
x
12 are an ordering of vertices of T with f
(
x
i
)
≤
f
(
x
i
+
1
), 1
≤
i
≤
11. Here ϵ
2
=
{
f
(
x
2
)
-
f
(
x
1
)
}
-
{
1
+
7
-
d
(
x
1
,
x
2
)
}
=
(
5
-
1
)
-
(
1
+
7
-
4
)
=
0, ϵ
3
=
0, ϵ
4
=
2, ϵ
5
=
1, ϵ
6
=
0, ϵ
7
=
0, ϵ
8
=
1, ϵ
9
=
0, ϵ
10
=
0, ϵ
11
=
2, ϵ
12
=
0, and d
(
f
)
=
∑
i
=
2
12
‍
d
(
x
i
,
x
i
-
1
)
=
d
(
x
2
,
x
1
)
+
d
(
x
3
,
x
2
)
+
d
(
x
4
,
x
3
)
+
d
(
x
5
,
x
4
)
+
d
(
x
6
,
x
5
)
+
d
(
x
7
,
x
6
) + d
(
x
8
,
x
7
)
+
d
(
x
9
,
x
8
)
+
d
(
x
10
,
x
9
)
+
d
(
x
11
,
x
10
)
+
d
(
x
12
,
x
11
)
=
4
+
7
+
1
+
5
+
2
+
2
+
2 + 3
+
3
+
3
+
4
=
36.Figure 1
A radio coloring of a tree of order12 and diameter 7.The following lemma gives the span of a radio coloring of a graph of ordern in terms of n, d, distance sum, and ϵ’s sum.Lemma 3.
For any radio coloringf of G, the span of f  r
c
d
(
f
)
=
f
(
x
n
)
=
(
n
-
1
)
(
1
+
d
)
-
∑
i
=
2
n
‍
d
(
x
i
,
x
i
-
1
)
+
∑
i
=
2
n
‍
ϵ
i
f
+
1, where x
i’s are arranged as in Definition 1.Proof.
Considerf
(
x
n
)
-
f
(
x
1
)
=
∑
i
=
2
n
‍
[
f
(
x
i
)
-
f
(
x
i
-
1
)
]
=
∑
i
=
2
n
‍
[
1
+
d
-
d
(
x
i
,
x
i
-
1
)
+
ϵ
i
f
] = (
n
-
1
)
(
1
+
d
)
-
∑
i
=
2
n
‍
d
(
x
i
,
x
i
-
1
)
+
∑
i
=
2
n
‍
ϵ
i
f.
Sincef
(
x
1
)
=
1, we get f
(
x
n
)
=
(
n
-
1
)
(
1
+
d
)
-
∑
i
=
2
n
‍
d
(
x
i
,
x
i
-
1
)
+
∑
i
=
2
n
‍
ϵ
i
f
+
1.Lemma3 says that to obtain a minimal radio coloring of a graph, one should maximize d
(
f
) and minimize ∑
i
=
2
n
‍
ϵ
i
f over all possible radio colorings of the graph. Since this fact is the basic concept to construct a minimal radio coloring, we express it as the theorem below.Theorem 4.
Ifg is a radio coloring of G such that ∑
i
=
2
n
‍
ϵ
i
g
=
0 and d
(
g
)
=
max
⁡
{
d
(
f
): f is a radio coloring of G
}, then g is a minimal radio coloring of G.Proof.
For any radio coloringf of G, Lemma 3 gives that r
c
d
(
f
)
=
(
n
-
1
)
(
1
+
d
)
-
d
(
f
)
+
∑
i
=
2
n
‍
ϵ
i
f. Then
(1)
r
c
d
G
=
min
⁡
{
r
c
d
(
f
)
:
f
is
a
radio
coloring
of
G
}
=
min
⁡
∑
i
=
2
n
‍
(
n
-
1
)
(
1
+
d
)
-
d
(
f
)
minnn
+
∑
i
=
2
n
‍
ϵ
i
f
:
f
is
a
radio
coloring
of
G
=
(
n
-
1
)
(
1
+
d
)
-
max
⁡
f
d
f
+
min
⁡
f
∑
i
=
2
n
‍
ϵ
i
f
=
n
-
1
1
+
d
-
d
g
since
ϵ
i
,
i
=
2,3
,
…
,
n
is
nonnegative
,
∑
i
=
2
n
‍
ϵ
i
g
=
0
=
r
c
d
g
.Now, we determine the radio number of anm-distant tree T with d
i
a
m
(
T
)
=
2
p
-
1, p
≥
2, m
≤
p
-
p
-
1, and the degrees of the vertices on the central path satisfy certain conditions (given in the theorem below).Theorem 5.
LetT be an m-distant tree of order n with a central path P: a
1
a
2
⋯
a
2
p
-
1
a
2
p, and satisfy (i)
m
≤
p
-
p
-
1;
(ii)
d
e
g
(
a
i
)
=
2, for i
=
2,3
,
…
,
m, 2
p
-
m
+
1,2
p
-
m
+
2
,
…
,
2
p;
(iii)
d
e
g
(
a
j
)
=
d
e
g
(
a
j
+
p
-
m
)
=
s
j
+
2, s
j
≥
0, j
=
m
+
1
,
m
+
2
,
…
,
p;
(iv)
for everya
l, l
=
m
+
1
,
m
+
2
,
…
,
2
p
-
m, the number of vertices at distance i and lying on a branch incident on a
l, 2
≤
i
≤
m, is a constant say t
i (t
i
≥
0).
Thenr
n
(
T
)
=
2
(
p
-
m
)
(
p
+
m
)
∑
i
=
2
m
‍
t
i
-
∑
i
=
2
m
‍
2
i
t
i
+
2
(
p
+
m
)
-
4
∑
i
=
m
+
1
p
‍
s
i
+
2
p
(
p
-
1
)
+
3.Proof.
The idea is to define a radio coloringf of T and show that f is minimal by Theorem 4. We first give an algorithm to order the vertices of T.
Algorithm  6
Step I. We make an ordering x
1
,
x
2
,
…
,
x
2
p of the vertices on the central path as a
p, a
2
p, a
p
-
1, a
2
p
-
1, a
p
-
2, a
2
p
-
2, …, a
1, a
p
+
1, that is, x
1
=
a
p, x
2
=
a
2
p
,
…
,
x
2
p
=
a
p
+
1.
Step II. Let x
l
1
,
x
l
2
,
…
,
x
l
2
p
-
2
m be equal to the vertices a
p, a
2
p
-
m, a
p
-
1, a
2
p
-
(
m
+
1
)
,
…
,
a
m
+
1, a
p
+
1, respectively. Let B
=
(
b
1
(
i
)
,
b
2
(
i
)
,
…
,
b
2
p
-
2
m
(
i
)
) be an ordered tuple of vertices in T
∖
P such that b
j
(
i
) is at distance i from P and lies on a branch incident on x
l
j, i
=
2,3
,
…
,
m, and j
=
1,2
,
…
,
2
p
-
2
m. So for any i, there are t
i disjoint such tuples, i
=
2,3
,
…
,
m. Consider the sequence S: x
2
p
+
1
,
x
2
p
+
2
,
…
,
x
r, where r
=
2
p
+
2
(
p
-
m
)
∑
i
=
2
m
‍
t
i.
Step III. We take i
=
m. In this case, there are t
m disjoint tuples B. Select an arbitrary such tuple B and use the first 2
p
-
2
m terms of the sequence S to name the vertices in B in order. For the next tuple B we use the next 2
p
-
2
m terms of the sequence S to name the vertices in B in order. We proceed like this until we cover all the t
m disjoint tuples.
Step IV. We name the vertices in T
∖
P which are at distance m
-
1 from P, in the similar manner. We proceed like this until we name all the vertices in T
∖
P and are of distance 2 from P.
Step V. Consider the sequence S
1
:
x
r
+
1
,
x
r
+
2
,
…
,
x
n. The terms in the beginning of S
1 are assigned (or named) to the distance one vertices in T
∖
P adjacent to x
l
1 and x
l
2 alternately (the number of distance one vertices in T
∖
P adjacent to x
l
i and x
l
i
+
1, 1
≤
i
≤
2
p
-
2
m
-
1 are equal). The next terms of S
1 are assigned to the distance one vertices in T
∖
P adjacent to x
l
3 and x
l
4 alternately, and so on, till we name all the vertices of T. Observe that n
=
2
p
+
(
2
p
-
2
m
)
∑
i
=
2
m
‍
t
i
+
2
∑
i
=
m
+
1
p
‍
s
i.
Nowx
1
,
x
2
,
…
,
x
n is an ordering of all the vertices of T.
Letf be a coloring to the vertices of T defined by
(2)
f
(
x
1
)
=
1
f
(
x
i
)
=
f
(
x
i
-
1
)
+
2
p
-
d
(
x
i
,
x
i
-
1
)
,
2
≤
i
≤
n
.
Before we prove that f is a minimal radio coloring of T, we give an illustration of f.
Example  7. In this example, we illustrate the above coloring f by considering the 3-distant tree T given in Figure 2
Herep
=
6, the central path P: a
1
a
2
⋯
a
12, m
=
3, t
2
=
1, t
3
=
2, s
4
=
3, s
5
=
1, s
6
=
2, x
1
=
a
6, x
2
=
a
12, x
3
=
a
5, x
4
=
a
11, x
5
=
a
4, x
6
=
a
10, x
7
=
a
3, x
8
=
a
9, x
9
=
a
2, x
10
=
a
8, x
11
=
a
1, x
12
=
a
7, x
l
1
=
a
6, x
l
2
=
a
9, x
l
3
=
a
5, x
l
4
=
a
8, x
l
5
=
a
4, x
l
6
=
a
7, S: x
13
,
x
14
,
…
,
x
30, and S
1: x
31
,
x
32
,
…
,
x
42. So the ordering of the vertices of this 3-distant tree is in Figure 3.
The assignmentf is given in Figure 4.
Continuation of the Proof of Theorem. We first show that f is a radio coloring. We need to check that |
f
(
x
i
)
-
f
(
x
j
)
|
≥
1
+
(
2
p
-
1
)
-
d
(
x
i
,
x
j
), 1
≤
i
≠
j
≤
n (we call this as radio condition). From the definition of f, radio condition holds true for pair of vertices x
i and x
i
-
1, 2
≤
i
≤
n. For 1
≤
i
≤
2
p,
(3)
f
x
i
+
2
-
f
x
i
=
f
(
x
i
+
2
)
-
f
(
x
i
+
1
)
+
f
(
x
i
+
1
)
-
f
(
x
i
)
=
2
p
-
d
(
x
i
+
2
,
x
i
+
1
)
+
2
p
-
d
(
x
i
+
1
,
x
i
)
=
4
p
-
{
d
(
x
i
+
2
,
x
i
+
1
)
+
d
(
x
i
+
1
,
x
i
)
}
=
4
p
-
{
2
p
+
1
}
=
2
p
-
1
≥
1
+
2
p
-
d
(
x
i
,
x
i
+
2
)
.
Since(4)
f
x
2
p
+
1
-
f
x
2
p
-
1
=
f
(
x
2
p
+
1
)
-
f
(
x
2
p
)
+
f
(
x
2
p
)
-
f
(
x
2
p
-
1
)
=
2
p
-
(
m
+
1
)
+
2
p
-
(
p
)
=
3
p
-
(
m
+
1
)
≥
2
p
-
1
,
radio condition holds true for all the pair of vertices x
i and x
j, where one of them is on the central path P and the other in T
∖
P.
Now,(5)
f
x
2
p
+
3
-
f
x
2
p
+
1
=
f
(
x
2
p
+
3
)
-
f
(
x
2
p
+
2
)
+
f
(
x
2
p
+
2
)
-
f
(
x
2
p
+
1
)
=
2
p
-
d
(
x
2
p
+
2
,
x
2
p
+
3
)
+
2
p
-
d
(
x
2
p
+
1
,
x
2
p
+
2
)
=
2
p
-
{
p
-
m
+
1
+
2
m
}
+
2
p
-
{
p
-
m
+
2
m
}
=
4
p
-
(
p
-
m
+
2
m
)
4
p
-
v
+
(
p
-
m
+
1
+
2
m
)
=
2
p
-
(
2
m
+
1
)
=
2
p
-
d
(
x
2
p
+
1
,
x
2
p
+
3
)
.
Since x
2
p
+
4
,
x
2
p
+
5
,
…
,
x
2
p
+
2
p
-
2
m are at least 2
m
+
1 distance apart from x
2
p
+
1 and have colors greater than f
(
x
2
p
+
3
), radio condition automatically holds true, and
(6)
f
x
2
p
+
2
p
-
m
-
f
x
2
p
+
1
=
∑
i
=
2
2
(
p
-
m
)
‍
f
(
x
2
p
+
i
)
-
f
(
x
2
p
+
i
-
1
)
=
2
p
(
2
(
p
-
m
)
-
1
)
-
∑
i
=
2
2
(
p
-
m
)
‍
d
(
x
2
p
+
i
,
x
2
p
+
i
-
1
)
=
4
p
2
-
4
p
m
-
2
p
-
2
(
p
-
m
)
-
2
2
(
p
+
m
+
p
+
m
+
1
)
+
p
+
m
=
2
p
2
-
(
4
m
+
2
)
p
+
2
m
(
m
+
1
)
+
1
.
If x
2
p
+
2
(
p
-
m
)
+
1 is at a distance m from P, then
(7)
f
x
2
p
+
2
p
-
m
+
1
-
f
(
x
2
p
+
1
)
=
f
x
2
p
+
2
p
-
m
+
1
-
f
x
2
p
+
2
p
-
m
+
2
p
2
-
4
m
+
2
p
+
2
m
m
+
1
+
1
=
2
p
-
2
m
+
1
+
2
p
2
-
4
m
+
2
p
+
2
m
m
+
1
+
1
=
2
p
-
m
2
≥
2
p
-
p
-
p
-
1
2
=
2
p
-
2
=
2
p
-
d
x
2
p
+
1
,
x
2
p
+
2
p
-
m
+
1
.
Since f
(
x
2
p
+
2
(
p
-
m
)
+
1
)
-
f
(
x
2
p
+
1
)
≥
2
p
-
2, radio condition holds true between x
2
p
+
1 and all other vertices.
Leti
=
2
p
+
(
2
p
-
2
m
)
t
m. Then x
i is the last vertex at distance m from P. Since, from the definition of f, radio condition holds true for x
i and x
i
+
1, and d
(
x
i
,
x
i
+
1
)
=
m
+
1
+
m
-
1
=
2
m
≤
d
(
x
i
,
x
i
+
j
), 2
≤
j
≤
2
p
-
2
m
-
1, radio condition automatically holds true between x
i and x
i
+
j, 2
≤
j
≤
2
p
-
2
m
-
1.
Sincef
(
x
i
+
1
)
-
f
(
x
i
)
=
2
p
-
{
m
+
(
m
-
1
)
+
1
}
=
2
(
p
-
m
), f
(
x
i
+
2
)
-
f
(
x
i
+
1
)
=
2
p
-
{
2
(
m
-
1
)
+
p
-
m
}
=
p
-
m
+
2, and f
(
x
i
+
3
)
-
f
(
x
i
+
2
)
=
2
p
-
{
2
(
m
-
1
)
+
p
-
m
+
1
}
=
p
-
m
+
1, we have
(8)
f
x
i
+
2
p
-
2
m
-
f
x
i
=
∑
l
=
2
2
p
-
2
m
‍
f
x
i
+
l
-
f
x
i
+
l
-
1
+
f
(
x
i
+
1
)
-
f
(
x
i
)
=
2
p
-
2
m
2
(
p
-
m
+
2
)
+
2
p
-
2
m
-
2
2
(
p
-
m
+
1
)
+
2
(
p
-
m
)
=
2
p
-
m
2
+
4
(
p
-
m
)
-
1
≥
2
p
-
1
=
2
p
-
d
(
x
i
,
x
i
+
2
p
-
2
m
)
.
In a similar manner, one can check the radio condition for the remaining pair of vertices. Therefore, f is a radio coloring. Next, we show that f is minimal. Let x and y be any two vertices of T. Then we get vertices a
i and a
j on the central path P such that x
=
a
i or x is on a branch incident on a
i, and y
=
a
j or y is on a branch incident on a
j. Then
(9)
d
(
x
,
y
)
=
|
j
-
i
|
,
if
x
=
a
i
and
y
=
a
j
|
j
-
i
|
+
j
1
,
if
x
=
a
i
and
y
lies
on
⁡
a
branch
and
is
j
1
distance
from
a
j
|
j
-
i
|
+
j
2
,
if
y
=
a
j
and
x
lies
on
⁡
a
branch
and
is
j
2
distance
from
a
i
|
j
-
i
|
+
j
1
+
j
2
,
if
x
and
y
lie
on
⁡
branches
and
are
j
2
and
j
1
distances
from
a
i
and
a
j
respectively
.
So, each term in the distance sum of a radio coloring contains two indices from {
1,2
,
…
,
2
p
} with different signs because from (9), distance between every pair of vertices contains |
j
-
i
|, i
,
j
∈
{
1,2
,
…
,
2
p
}. Since there are n
-
1 terms in the distance sum, it contains 2
(
n
-
1
) elements from the set {
1,2
,
…
,
2
p
} with half positive and half negative sign. Also, the indices 1,2
,
3
,
…
,
m and 2
p
-
m
-
1
,
2
p
-
m
-
2
,
…
,
2
p
-
1,2
p occur at most twice, and the index j
∈
{
m
+
1
,
m
+
2
,
…
,
2
p
-
m
} occur at most 2
∑
i
=
2
m
‍
t
i
+
s
j
+
2 times, where d
e
g
(
a
j
)
=
d
e
g
(
a
j
+
p
-
m
)
=
s
j
+
2. So, the possible maximum distance sum is 2
(
∑
i
=
2
m
‍
t
i
+
s
m
+
2
+
1
)
p
+
2
-
m
+
2 + 2
∑
i
=
2
m
‍
t
i
+
s
m
+
3
+
1
p
+
3
-
m
+
3
+
⋯
+
2
∑
i
=
2
m
‍
t
i
+
s
p
-
1
+
1
[
(
2
p
-
(
m
+
1
)
)
-
(
p
-
1
)
] + 2
∑
i
=
2
m
‍
t
i
+
s
p
+
1
(
2
p
-
m
)
-
2
∑
i
=
2
m
‍
t
i
+
s
p
+
(
1
/
2
)
(
p
) + 2
∑
i
=
2
m
‍
t
i
+
s
m
+
1
+
(
1
/
2
)
(
p
+
1
)
-
2
∑
i
=
2
m
‍
t
i
+
s
m
+
1
+
1
(
m
+
1
)
+
2
(
2
p
+
2
p
-
1
+
2
p
-
2 + ⋯
+
2
p
-
(
m
-
1
)
)
-
2
(
1
+
2
+
3
+
⋯
+
m
)
+
2
(
p
-
m
)
∑
i
=
2
m
‍
2
i
t
i
+
2
∑
i
=
m
+
1
p
‍
2
s
i
-
1.
Now, the distance sum(10)
d
f
=
∑
i
=
2
n
‍
d
(
x
i
,
x
i
-
1
)
=
∑
i
=
2
2
p
‍
d
x
i
,
x
i
-
1
+
∑
i
=
2
p
+
1
2
p
+
(
2
p
-
2
m
)
t
m
‍
d
x
i
,
x
i
-
1
+

∑
i
=
2
p
+
(
2
p
-
2
m
)
t
m
+
1
2
p
+
(
2
p
-
2
m
)
t
m
+
(
2
p
-
2
m
)
t
m
-
1
‍
d
x
i
,
x
i
-
1
+
⋯
+

∑
i
=
2
p
+
(
2
p
-
2
m
)
t
m
+
(
2
p
-
2
m
)
t
m
-
1
+
⋯
+
(
2
p
-
2
m
)
t
3
+
1
2
p
+
(
2
p
-
2
m
)
t
m
+
(
2
p
-
2
m
)
t
m
-
1
+
⋯
+
(
2
p
-
2
m
)
t
3
+
(
2
p
-
2
m
)
t
2
d
x
i
,
x
i
-
1
+


∑
i
=
2
p
+
(
2
p
-
2
m
)
t
m
+
(
2
p
-
2
m
)
t
m
-
1
+
⋯
+
(
2
p
-
2
m
)
t
3
+
(
2
p
-
2
m
)
t
2
+
1
n
d
x
i
,
x
i
-
1
,
where n
=
2
p
+
∑
i
=
2
m
‍
(
2
p
-
2
m
)
t
i
+
2
∑
i
=
m
+
1
p
‍
s
i coincides with the possible maximum distance sum above and is equal to 2
(
p
-
m
)
(
p
-
m
)
∑
i
=
2
m
‍
t
i
+
∑
i
=
2
m
‍
2
i
t
i
+
2
(
p
-
m
)
+
4
∑
i
=
m
+
1
p
‍
2
s
i
+
2
p
2
-
2.
One observes that∑
i
=
2
n
‍
ϵ
i
f
=
0. Therefore, from Theorem 4, the radio coloring f is minimal and
(11)
r
c
2
p
-
1
T
=
r
c
2
p
-
1
(
f
)
=
n
-
1
1
+
2
p
-
1
-
∑
i
=
2
n
‍
d
x
i
,
x
i
-
1
+
1
=
2
p
+
2
p
-
m
∑
i
=
2
m
‍
t
i
+
2
∑
i
=
m
+
1
p
‍
s
i
-
1
2
p
-
∑
i
=
2
n
‍
d
x
i
,
x
i
-
1
+
1
=
2
p
-
m
p
+
m
∑
i
=
2
m
‍
t
i
-
∑
i
=
2
m
‍
2
i
t
i
+
2
(
p
+
m
)
-
4
∑
i
=
m
+
1
p
‍
s
i
+
2
p
(
p
-
1
)
+
3
.Figure 2
TreeT to illustrate Theorem 5.Figure 3
Ordering of vertices ofT obtained from Theorem 5.Figure 4
Radio coloring ofT obtained from Theorem 5.As a consequence of the above theorem, we determine the radio number of a class of caterpillars (1-distant trees). In the corollary below, we find radio number of caterpillars of odd diameter in which the degrees of every pair of nonpendant vertices on the central path lying at distance p
-
1 apart have the same degree (where 2
p is the total number of vertices on the central path).Corollary 8.
LetC be a caterpillar of order n and with a central path P
:
a
1
a
2
a
3
⋯
a
2
p. If d
e
g
(
a
i
)
=
d
e
g
(
a
p
+
i
-
1
)
=
s
i
+
2, s
i
≥
0, i
=
2,3
,
…
,
p, then
(12)
r
n
(
C
)
=
2
p
-
1
∑
i
=
2
p
‍
s
i
+
p
p
-
1
+
3
.Proof.
This ism
=
1 case of Theorem 5. The ordering of vertices in this case includes Step I and Step V of algorithm in the proof of Theorem 5 with only variation that if a vertex on the central path is not adjacent to any pendant vertex, then we move to the next possible vertex.Example 9.
In this example, we illustrate Corollary8 by considering the caterpillar given in Figure 5.Figure 5
A caterpillar to illustrate Corollary8.Herep
=
6, the central path P: a
1
a
2
⋯
a
12 and s
2
=
2
,
s
3
=
0
,
s
4
=
3
,
s
5
=
2. So the ordering of vertices of the caterpillar is illustrated in Figure 6 and the coloring f is given in Figure 7.Figure 6
Ordering of vertices of the caterpillar given in Figure5.Figure 7
Radio coloringf of the caterpillar given in Figure 5.The corollary below is also a consequence of Theorem5 in which we find the radio number of caterpillars of odd diameter in which all nonpendant vertices on the central path are of the same degree.Corollary 10.
LetC be a caterpillar of order n with a central path P: a
1
a
2
a
3
⋯
a
2
p. If d
e
g
(
a
i
)
=
s
+
2, i
=
2,3
,
…
,
2
p
-
1, s
≥
0, then r
n
(
C
)
=
2
[
s
(
p
-
1
)
2
+
p
(
p
-
1
)
]
+
3.Proof.
One can prove this result by substitutings
i
=
s, i
=
2,3
,
…
,
p in Corollary 8.Example 11.
In this example we illustrate Corollary10 by considering the caterpillar given in Figure 8.Figure 8
A caterpillar for illustration of Corollary10.Herep
=
6, the central path P: a
1
a
2
⋯
a
12 and t
=
2. So the ordering of vertices of the caterpillar is illustrated in Figure 9 and the coloring f is given in Figure 10.Figure 9
Ordering of vertices of the caterpillar given in Figure8.Figure 10
Minimal radio coloring of the caterpillar given in Figure8.



---

*Source: 486354-2014-12-15.xml*