Radio $k$-labeling of paths

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$.

Keywords

• Channel assignment
• Radio $k$-labeling
• Radio $k$-chromatic number
• span

References

1. [1] G.J. Chang and D. Kuo, The $L(2, 1)$-labelling problem on graphs, SIAM J. Discrete Math. 9, 309–316, 1996.
2. [2] G.J. Chang, C. Lu, and S. Zhou, Distance-two labellings of Hamming graphs, Discrete Appl. Math. 157, 1896–1904, 2009.
3. [3] G. Chartrand, D. Erwin, and P. Zhang, Radio antipodal colorings of cycles, Proceedings of the Thirty-first Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2000) 144, 129–141, 2000.
4. [4] G. Chartrand, D. Erwin, and P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl. 43, 43–57, 2005.
5. [5] G. Chartrand, L. Nebesky, and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph. Theory, 24, 5–21, 2004.
6. [6] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
7. [7] J.P. Georges, D.W. Mauro, and M.I. Stein, Labelling products of complete graphs with a condition at distance two, SIAM J. Discrete Math. 14, 28–35, 2001.
8. [8] J.R. Griggs and X.T. Jin, Real number graph labelling with distance conditions, SIAM J. Discrete Math. 20, 302–327, 2006.

9. [9] J.R. Griggs, and D. Král’, Graph labellings with variable weights, a survey, Discrete Appl. Math. 157, 2646–2658, 2009.
10. [10] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5, 586–595, 1992.
11. [11] W.K. Hale, Frequency assignment, theory and application, Proc. IEEE, 68, 1497– 1514, 1980.
12. [12] J.v.d. Heuvel, R. Leese, and M. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory, 29, 263–283, 1998.
13. [13] J.S.-T. Juan and D.D.-F. Liu, Antipodal labelings for cycles, Ars Combin. 103, 81–96, 2012.
14. [14] M. Kchikech, R. Khennoufa, and O. Togni, Linear and cyclic radio k-labelings of trees, Discuss. Math. Graph Theory, 27 (1), 105–123, 2007.
15. [15] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
16. [16] R. Khennoufa and O. Togni, The radio antipodal and radio numbers of the hypercube, Ars Combin. 102, 447–461, 2011.
17. [17] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohem. 130 (3), 277–282, 2005.
18. [18] S.R. Kola and P. Panigrahi, Nearly antipodal chromatic number $ac'(P_n)$ of the path, Math. Bohem. 134 (1), 77–86, 2009.
19. [19] S.R. Kola and P. Panigrahi, On radio $(n−4)$-chromatic number of the path $P_n$, AKCE Int. J. Graphs Comb. 6 (1), 209–217, 2009.
20. [20] D. Král’, The channel assignment problem with variable weights, SIAM J. Discrete Math. 20, 690–704, 2006.
21. [21] X. Li, V. Mak, and S. Zhou, Optimal radio labellings of complete m-ary trees, Discrete Appl. Math. 158, 507–515, 2010.
22. [22] D.D.-F. Liu, Radio number for trees, Discrete Math. 308, 1153–1164, 2008.
23. [23] D.D.-F. Liu and M. Xie, Radio number for square of cycles, Congr. Numer. 169, 105–125, 2004.
24. [24] D.D.-F. Liu and M. Xie, Radio number for square paths, Ars Combin. 90, 307–319, 2009.
25. [25] D.D.-F. Liu and X. Zhu, Multi-level distance labelings for paths and cycles, SIAM J. Discrete Math. 19, 610–621, 2005.
26. [26] M. Morris-Rivera, M. Tomova, C.Wyels, and Y. Yeager, The radio number of $C_{n}\times C_{n}$, Ars Combin. 103, 81–96, 2012.
27. [27] J.P. Ortiz, P. Martinez, M. Tomova, and C.Wyels, Radio numbers of some generalized prism graphs, Discuss. Math. Graph Theory, 31 (1), 45–62, 2011.
28. [28] V.S. Reddy and V.K. Iyer, Upper bounds on the radio number of some trees, Int. J. Pure Applied Math. 71 (2), 207–215, 2011.
29. [29] L. Saha and P. Panigrahi, A graph Radio k-coloring algorithm, Lecture notes in Computer Science 7643, 125–129, 2012.
30. [30] L. Saha and P. Panigrahi, On the Radio number of Toroidal grids, Australian J. Combin. 55, 273–288, 2013.
31. [31] L. Saha and P. Panigrahi, A lower bound for radio k-chromatic number, Discrete Appl. Math. 192, 87–100, 2015.
32. [32] U. Sarkar and A. Adhikari, On characterizing radio k-coloring problem by path covering problem, Discrete Math 338 (4), 615–620, 2015.
33. [33] P. Zhang, Radio labellings of cycles, Ars Combin 65, 21–32, 2002.
34. [34] S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theoret. Comput. Sci. 310, 501–511, 2004.
35. [35] S. Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Discrete Math. 19, 985–1003, 2006.
36. [36] S. Zhou, A distance-labelling problem for hypercubes, Discrete Appl. Math. 156, 2846– 2854, 2008.