# Radio Number for Total Graph of Paths

Authors: S. K. Vaidya; D. D. Bantva
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

A radio labeling of a graphG is a function f from the vertex set V(G) to the set of nonnegative integers such that |f(u)-f(v)|≥diam(G)+1-dG(u,v), where diam(G) and dG(u,v) are diameter and distance between u and v in graph G, respectively. The radio number rn(G) of G is the smallest number k such that G has radio labeling with max{f(v):v∈V(G)}=k. We investigate radio number for total graph of paths.


---

## Body

## 1. Introduction

In a telecommunication system to design radio networks, the interference constraints between a pair of transmitters play a vital role. For the transmitters of radio network, we seek to assign channels such that the network fulfills all the interference constraints. The assignment of channels to the transmitters is popularly known as channel assignment problem which was introduced by Hale [1]. For radio network if we assume that the frequencies are uniformly distributed in the spectrum then the frequency span determines the bandwidth allocated for the assignment. In this case, the interference between two transmitters is closely related with the geographic location of the transmitters. Earlier designer of radio networks considered only the two-level interference, namely, major and minor. They classified a pair of transmitters as very close transmitters if the interference level between them is major and close transmitters if the interference level between them is minor.To solve the channel assignment problem, the interference graph is developed and assignment of channels converted into graph labeling (a graph labeling is an assignment of label to each vertex according to certain rule). In interference graph, the transmitters are represented by the vertices, and two vertices are joined by an edge if corresponding transmitters have the major interference while two transmitters have minor interference then corresponding vertices are at distance two, and there is no interference between transmitters if they are at distance three or beyond it. In other words,very close transmitters are represented by adjacent vertices, and close transmitters are represented by the vertices which are at distance two apart. In fact, Roberts [2] proposed that a pair of transmitters which has minor interference must receive different channels and a pair of transmitters which has major interference must receive channels that are at least two apart. Motivated through this problem Griggs and Yeh [3] introduced L(2,1)-labeling in which channels are related with the nonnegative integers.Definition 1.
A distance two labeling (orL(2,1)-labeling) of a graph G=(V(G),E(G)) is a function f from vertex set V(G) to the set of nonnegative integers such that the following conditions are satisfied:(1)
|f(u)-f(v)|≥2 if d(u,v)=1,(2)
|f(u)-f(v)|≥1 if d(u,v)=2.The span off is defined as max{|f(u)-f(v)|:u,v∈V(G)}. The λ-number for a graph G, denoted by λ(G), is the minimum span of a distance two labeling for G. The L(2,1)-labeling is explored in past two decades by many researchers like Yeh [4], Sakai [5], Chang and Kuo [6], Vaidya et al. [7], and Vaidya and Bantva [8].But as time passed, practically it has been observed that the interference among transmitters might go beyond two levels. Radio labeling extends the number of interference level considered inL(2,1)—labeling from two to the largest possible—the diameter of G. The diameter of G denoted by diam(G) or simply by d is the maximum distance among all pairs of vertices in G. Motivated through the problem of channel assignment of FM radio stations, Chartrand et al. [9] introduced the concept of radio labeling of graph as follows.Definition 2.
A radio labelingf of G is an assignment of positive integers to the vertices of G satisfying
(1)|f(u)-f(v)|≥diam(G)+1-dG(u,v),∀u,v∈V(G).The radio number denoted byrn(G) is the minimum span of a radio labeling for G. Note that when diam(G) is two then radio labeling and distance two labeling are identical.Investigating the radio number of a graph is an interesting and challenging task as well. So far the radio number is known only for handful of graph families. Liu and Zhu [10] have given the radio labeling for paths and cycles. Liu and Xie [11, 12] also studied the case of radio labeling for square of paths and cycles while Der-Fen Liu [13] has given a lower bound for radio number of trees and presented a class of trees achieving the lower bound.Notice that the expansion of radio network according to certain rule is equivalent to saying that the expansion of interference graph by means of specific graph operation. The expansion of existing network and to determine the radio number for the expanded network is also an interesting task. At the same time, it is also important to relate the radio number of existing network with the expanded network. In this paper, we take up the issue of expansion of linear network in the context of total graph of path and also investigate the radio number for the same.Definition 3.
The total graph of a graphG is the graph whose vertex set is V(G)∪E(G) and two vertices are adjacent whenever they are either adjacent or incident in G. The total graph of G is denoted by T(G).From the definition of total graph, it is clear that the diameter ofT(Pn) is same as diameter of Pn, and the center of graph T(Pn) is K1 if n=2k+1 and K3 if n=2k. Terms not defined here are used in the sense of West [14].


## 2. Main Results

The radio number of path (linear transmitter network) is investigated by Liu and Zhu [10] as stated in the following result.Theorem 4.
For anyn≥3,
(2)rn(Pn)={2k(k-1)+1ifn=2k2k2+2ifn=2k+1.Now we focus upon the radio number of the linear network which is expanded by means of total graph operation onPn. Throughout this work, we denote a path with n vertices by Pn, where V(Pn)={v1,v2,…,vn} and E(Pn)={ei=vivi+1:i=1,2,…,n-1}.For the pathP2k, let vL0 and vR0 be the centers. Let vL1,vL2,…,vL(k-1) be the vertices on left side, and vR1,vR2,…,vR(k-1) are the vertices on right side with respect to the centers. The edges are e0=(vL0,vR0),eL1=(vL0,vL1),eL2=(vL1,vL2),…,eL(k-1)=(vL(k-2),vL(k-1)),eR1=(vR0,vR1),eR2=(vR1,vR2),…,eR(k-1)=(vR(k-2),vR(k-1)). Then the vertex set of total graph of Pn is V(T(Pn))={vL0,vR0,vL1,vL2,…,vL(k-1),vR1,vR2,…,vR(k-1),e0,eL1,eL2,…,eL(k-1),eR1,eR2,…,eR(k-1)}. For the consistency in notation, we rename the vertices e0, eL1, eL2,…,eL(k-1), eR1, eR2,…,eR(k-1) by v0′, vL1′, vL2′,…,vL(k-1)′, vR1′, vR2′,…,vR(k-1)′, respectively.For the pathP2k+1, let v0 be the center. Let vL1, vL2,…,vLk be the vertices on left side, and vR1, vR2,…,vRk are the vertices on right side with respect to the center. The edges are eL1=(v0,vL1),eL2=(vL1,vL2),…,eLk=(vL(k-1),vLk),eR1=(v0,vR1),eR2=(vR1,vR2),…,eRk=(vR(k-1),vRk). Then the vertex set of total graph of Pn is V(T(Pn))={v0,vL1,vL2,…,vLk,vR1,vR2,…,vRk,eL1,eL2,…,eLk,eR1,eR2,…,eRk}. For the consistency in notation, we rename the vertices eL1, eL2,…,eLk, eR1, eR2,…,eRk by vL1′, vL2′,…,vLk′, vR1′, vR2′,…,vRk′, respectively.Let forP2k, V(T(Pn))=VL∪VR∪VL′∪VR′, where
(3)VL={vL0,vL1,vL2,…,vL(k-1)},VR={vR0,vR1,vR2,…,vR(k-1)},VL′={v0′,vL1′,vL2′,…,vL(k-1)′},VR′={v0′,vR1′,vR2′,…,vR(k-1)′}.Let forP2k+1, V(T(Pn))=VL∪VR∪VL′∪VR′, where
(4)VL={v0,vL1,vL2,…,vLk},VR={v0,vR1,vR2,…,vRk},VL′={vL1′,vL2′,…,vLk′},VR′={vR1′,vR2′,…,vRk′}.For the graphT(Pn), we say two vertices u and v are on opposite side if u∈VL or VL′ and v∈VR or VR′.Define the level functionL:V(T(Pn))→W, where W is the set of whole numbers with respect to a center vertex w by
(5)L(u)=d(w,u)foranyu∈V(T(Pn)).In graphT(Pn), the maximum level is k-1 if n=2k and k if n=2k+1.Observation 1.
ForT(Pn), (1)
|V(T(Pn))|={4k-1,ifn=2k4k+1,ifn=2k+1(2)
d(u,v)≤{L(u)+L(v)+1,ifn=2kL(u)+L(v),ifn=2k+1Theorem 5.
Letf be an assignment of distinct nonnegative integers to V(T(Pn)), where n=2k and {u1,u2,u3,…,up} be the ordering of V(T(Pn)) such that f(ui)<f(ui+1) defined by f(u1)=0 and f(ui+1)=f(ui)+d+1-d(ui,ui+1). If d(ui,ui+1)≤k+1 and d(ui,ui+1)≠d(ui+1,ui+2), for any 1≤i≤p-2 then f is a radio labeling.Proof.
Letf be an assignment of distinct nonnegative integers to V(T(Pn)) such that f(u1)=0, f(ui+1)=f(ui)+d+1-d(ui,ui+1), for any 1≤i≤p-1 and d(ui,ui+1)≤k+1 with d(ui,ui+1)≠d(ui+1,ui+2) for any 1≤i≤p-2 holds, where k=n/2.
Now we want to prove thatf is a radio labeling. That is, for any i≠j, |f(uj)-f(ui)|≥d+1-d(ui,uj).
For eachi=1,2,…,p-1, let fi=f(ui+1)-f(ui). Let j≥i+2 then
(6)f(uj)-f(ui)=fi+fi+1+⋯+fj-1=(j-i)(d+1)-d(ui,ui+1)-d(ui+1,ui+2)-⋯-d(uj-1,uj).
Ifn=2k, then d=2k-1.
Subcase 1 (if
j
-
i
is even). Consider
(7)f(uj)-f(ui)≥(j-i)(d+1)-j-i2(k+1)-j-i2(k)=(j-i)(2k)-(j-i)(k)-j-i2=(j-i)(k)-j-i2≥d+1-d(ui,uj).Subcase 2 (ifj-iis odd). Consider
(8)f(uj)-f(ui)≥(j-i)(d+1)-j-i+12(k+1)-j-i-12(k)≥d+1-d(ui,uj).
Thus, in both the subcasesf is a radio labeling and hence the result.Theorem 6.
LetT(Pn) be a total graph of path Pn on n vertices and k=⌊n/2⌋. Then rn(T(Pn))≥4k(k-1)+2 if n=2k.Proof.
Letf be an optimal radio labeling for T(P2k), where f(u1)=0<f(u2)<f(u3)<⋯<f(up). Then f(ui+1)-f(ui)≥(d+1)-d(ui,ui+1), for all 1≤i≤p-1. Summing these p-1 inequality, we get
(9)rn(T(P2k))=f(up)≥(p-1)(d+1)-∑i=1p-1d(ui,ui+1).
ForT(P2k), we have
(10)∑i=1p-1‍d(ui,ui+1)≤∑i=1p-1[L(ui)+L(ui+1)+1]=2∑u∈V(G)‍L(u)-L(u1)-L(up)+(p-1)=2∑u∈V(G)‍L(u)+(p-1).
Substituting (10) in (9), we get
(11)rn(T(P2k))=f(up)≥(p-1)(d+1)-2∑u∈V(G)‍L(u)-(p-1).
ForT(P2k), p=4k-1, d=2k-1 and ∑u∈V(G)‍L(u)=2k(k-1)(12)rn(T(P2k))=f(up)≥(4k-1-1)(2k-1+1)-4(k(k-1))-(4k-1-1)=8k2-4k-4k2+4k-4k+2=4k2-4k+2=4k(k-1)+2.
Thus,rn(T(Pn))≥4k(k-1)+2 if n=2k.Theorem 7.
LetT(Pn) be a total graph of path Pn on n vertices and k=⌊n/2⌋. Then rn(T(Pn))≤4k(k-1)+2 if n=2k.Proof.
ForT(P2k), define f:V(T(P2k))→{0,1,2,…,4k(k-1)+2} by f(u1)=0 and f(ui+1)=f(ui)+d+2-L(ui)-L(ui+1) for all 1≤i≤p-1 as per following ordering of vertices:
(13)vL0→vR(k-1)′→vL1→vR(k-2)′→vL2→⋯→vR1′→vL(k-1)→vR0→vL(k-1)′→vR1→vL(k-2)′→vR2→⋯→vL1′→vR(k-1)→v0′.
Thus, it is possible to assign labeling to the vertices ofT(P2k) with span equal to the lower bound satisfying the condition of Theorem 5 and hence f is a radio labeling.Theorem 8.
LetT(Pn) be a total graph of path Pn on n vertices and k=⌊n/2⌋. Then rn(T(Pn))=4k(k-1)+2 if n=2k.Proof.
The proof follows from Theorems6 and 7.Theorem 9.
LetT(Pn) be a total graph of path Pn on n vertices and k=⌊n/2⌋. Then rn(T(Pn))≥4k2+1 if n=2k+1.Proof.
Letf be an optimal radio labeling for T(P2k+1), where f(u1)=0<f(u2)<f(u3)<⋯<f(up). Then f(ui+1)-f(ui)≥(d+1) − d(ui,ui+1), for all 1≤i≤p-1. Summing these p-1 inequality, we get
(14)rn(T(P2k+1))=f(up)≥(p-1)(d+1)-∑i=1p-1d(ui,ui+1).
ForT(P2k+1), we have
(15)∑i=1p-1d(ui,ui+1)≤∑i=1p-1[L(ui)+L(ui+1)]=2∑u∈V(G)L(u)-L(u1)-L(up)=2∑u∈V(G)L(u)-1.
Substituting (15) in (14), we get
(16)rn(T(P2k+1))=f(up)≥(p-1)(d+1)-2∑u∈V(G)L(u)+1.
ForT(P2k+1), p=4k+1, d=2k and ∑u∈V(G)‍L(u)=2k(k+1),
(17)rn(T(P2k+1))=f(up)≥(4k+1-1)(2k+1)-4(k(k+1))+1=8k2+4k-4k2-4k+1=4k2+1.
Thus,rn(T(Pn))≥4k2+1 if n=2k+1.Theorem 10.
LetT(Pn) be a total graph of path Pn on n vertices and k=⌊n/2⌋. Then rn(T(Pn))≤4k2+3 if n=2k+1.Proof.
ForT(P2k+1), define f:V(T(P2k+1))→{0,1,2,…,4k2+3} by f(u1)=0 and f(ui+1)=f(ui)+d+1-L(ui)-L(ui+1) for all 1≤i≤p-1 as per following ordering of vertices:
(18)v0→vLk→vRk′→vL1′→vR(k-1)→vL2′→vR(k-2)→⋯→vR1→vLk′→vRk→vR1′→vL(k-1)→vR2′→vL(k-2)→⋯→vR(k-1)′→vL1.
Thus, it is possible to assign labeling to the vertices ofT(P2k+1) with span two more than the lower bound which is a radio labeling and hence rn(T(Pn))≤4k2+3 if n=2k+1.Example 11.
In Figure1, the ordering of the vertices and optimal radio labeling for T(P10) is shown.
(19)vL0→vR4′→vL1→vR3′→vL2→vR2′→vL3→vR1′→vL4→vR0→vL4′→vR1→vL3′→vR2→vL2′→vR3→vL1′→vR4→v0′.Figure 1
rn
(
T
(
P
10
)
)
=
82.Example 12.
In Figure2, the ordering of the vertices and optimal radio labeling for T(P11) is shown.
(20)v0→vL5→vR5′→vL1′→vR4→vL2′→vR3→vL3′→vR2→vL4′→vR1→vL5′→vR5→vR1′→vL4→vR2′→vL3→vR3′→vL2→vR4′→vL1.Figure 2
rn
(
T
(
P
11
)
)
=
103.


## 3. Open Problem

In connection with Theorems9 and 10, we feel that it is not possible to find the radio number with span equal to the lower bound but radio labeling for T(P2k+1) exists with span two more than the lower bound. We strongly believe that in case of T(P2k+1), the span will exceed than the lower bound. This feeling gives rise to an interesting problem to investigate exact radio number for T(P2k+1), we pose the following conjecture.Conjecture 13.
Consider(21)rn(T(P2k+1))=4k2+3.


## 4. Concluding Remarks

The establishment of radio transmitters network which is free of interference is the demand of the current time. It has also posed some new challenges. We take up this problem in the context of total graph of paths. We completely determine the radio number of total graph of pathT(P2k). The derived results are applicable for the expansion of linear network of transmitters.



---

*Source: 326038-2013-01-13.xml*