Yapay Zeka Hızlı Bakış & Çıkarımlar
AI InsightAlso an improvement of existing lower bound of $rc_{k}(P_n)$ has been presented for all values of $k$.
📌 3 Maddede Bu Makale
Abstract
The Channel Assignment Problem (CAP) is the problem of assigning channels (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=(V(G),\,E(G))$ and a positive integer $k$ with $1\leq k\leq {\rm diam(G)}$, a radio $k$-labeling of $G$is a mapping $f \colon V(G)\rightarrow \{0,\,1,\,2,\ldots\}$ such that $|f(u)-f(v)|\geq k+1-d(u,v)$ for each pair of distinct vertices $u$ and $v$ of $G$, where ${\rm diam(G)}$ is the diameter of $G$ and $d(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}(G)$, is the minimum of spans of all possible radio $k$-labelings of $G$. This article presents the exact value of $rc_{k}(P_n)$ for even integer $k\in\left\{\left\lceil\frac{2(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}(P_n)$ has been presented for all values of $k$.