Previous |  Up |  Next


radio antipodal colouring; radio number; distance labeling
The radio antipodal number of a graph $G$ is the smallest integer $c$ such that there exists an assignment $f\: V(G)\rightarrow \lbrace 1,2,\ldots ,c\rbrace $ satisfying $|f(u)-f(v)|\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.
[1] G. Chartrand, D. Erwin, F. Harary, P. Zhang: Radio labelings of graphs. Bull. Inst. Combin. Appl. 33 (2001), 77–85. MR 1913399
[2] G. Chartrand, D. Erwin, P. Zhang: Radio antipodal colorings of cycles. Congr. Numerantium 144 (2000), 129–141. MR 1817928
[3] G. Chartrand, D. Erwin, P. Zhang: Radio antipodal colorings of graphs. Math. Bohem. 127 (2002), 57–69. MR 1895247
[4] G. Chartrand, L. Nebeský, P. Zhang: Radio $k$-colorings of paths. Discuss. Math. Graph Theory 24 (2004), 5–21. DOI 10.7151/dmgt.1209 | MR 2118291
[5] D. Kuo, J.-H. Yan: On $L(2,1)$-labelings of Cartesian products of paths and cycles. Discrete Math. 283 (2004), 137–144. DOI 10.1016/j.disc.2003.11.009 | MR 2061491
[6] D. Liu, X. Zhu: Multi-level distance labelings for paths and cycles. (to appear).
Partner of
EuDML logo