Radio $k$-labeling of paths

Laxman SAHA; Satyabrata DAS; Kinkar Chandra DAS; Kalishankar TİWARY

doi:10.15672/hujms.573315

Radio $k$-labeling of paths

Authors : Laxman SAHA, Satyabrata DAS, Kinkar Chandra DAS, Kalishankar TİWARY

Pages : 1926-1943

Doi:10.15672/hujms.573315

View : 98 | Download : 10

Publication Date : 2020-12-08

Article Type : Research Paper

Abstract :The Channel Assignment Problem insert ignore into journalissuearticles values(CAP); is the problem of assigning channels insert ignore into journalissuearticles values(non-negative integers); to the transmitters in an optimal way such that interference is avoided. The problem, often modeled as a labeling problem on the graph where vertices represent transmitters and edges indicate closeness of the transmitters. A radio $k$-labeling of graphs is a variation of CAP. For a simple connected graph $G=insert ignore into journalissuearticles values(Vinsert ignore into journalissuearticles values(G);,\,Einsert ignore into journalissuearticles values(G););$ and a positive integer $k$ with $1\leq k\leq {\rm diaminsert ignore into journalissuearticles values(G);}$, a radio $k$-labeling of $G$is a mapping $f \colon Vinsert ignore into journalissuearticles values(G);\rightarrow \{0,\,1,\,2,\ldots\}$ such that $|finsert ignore into journalissuearticles values(u);-finsert ignore into journalissuearticles values(v);|\geq k+1-dinsert ignore into journalissuearticles values(u,v);$ for each pair of distinct vertices $u$ and $v$ of $G$, where ${\rm diaminsert ignore into journalissuearticles values(G);}$ is the diameter of $G$ and $dinsert ignore into journalissuearticles values(u,v);$ is the distance between $u$ and $v$ in $G$. The \emph{span } of a radio $k$-labeling $f$ is the largest integer assigned to a vertex of $G$. The \emph{radio $k$-chromatic number} of $G$, denoted by $rc_{k}insert ignore into journalissuearticles values(G);$, is the minimum of spans of all possible radio $k$-labelings of $G$. This article presents the exact value of $rc_{k}insert ignore into journalissuearticles values(P_n);$ for even integer $k\in\left\{\left\lceil\frac{2insert ignore into journalissuearticles values(n-2);}{5}\right\rceil, \ldots,\,n-2\right\}$ and odd integer $k\in\left\{\left\lceil\frac{2n+1}{7}\right\rceil,\ldots,\,n-1\right\}$, i.e., at least $65\%$ cases the radio $k$-chromatic number of the path $P_n$ are obtain for fixed but arbitrary values of $n$. Also an improvement of existing lower bound of $rc_{k}insert ignore into journalissuearticles values(P_n);$ has been presented for all values of $k$.
Keywords : Channel assignment, Radio k labeling, Radio k chromatic number, span

ORIGINAL ARTICLE URL