Advanced Search

The radio antipodal number of a graph $G$ is the smallest integer $c$ such that there exists an assignment $fV\left(G\right)\to \{1,2,...,c\}$ satisfying $\left|f\right(u)-f(v\left)\right|\ge D-d(u,v)$ for every two distinct vertices $u$ and $v$ of $G$, where $D$ is the diameter of $G$. In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin and P. Zhang, Math. Bohem. 127 (2002), 57–69]. We also show the connections between this colouring and radio labelings.

Frequency planning consists in allocating frequencies to the transmitters of a cellular network so as to ensure that no pair of transmitters interfere. We study the problem of reducing interference by modeling this by a radio k-labeling problem on graphs: For a graph G and an integer k ≥ 1, a radio k-labeling of G is an assignment f of non negative integers to the vertices of G such that $|f\left(x\right)-f\left(y\right)|\ge k+1-d_G(x,y)$, for any two vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. The radio k-chromatic number is...

Motivated by problems in radio channel assignments, we consider radio k-labelings of graphs. For a connected graph G and an integer k ≥ 1, a linear radio k-labeling of G is an assignment f of nonnegative integers to the vertices of G such that $|f\left(x\right)-f\left(y\right)|\ge k+1-d_G(x,y)$, for any two distinct vertices x and y, where $d_G(x,y)$ is the distance between x and y in G. A cyclic k-labeling of G is defined analogously by using the cyclic metric on the labels. In both cases, we are interested in minimizing the span of the labeling. The linear...