Research Article
BibTex RIS Cite
Year 2020, Volume: 49 Issue: 6, 1926 - 1943, 08.12.2020
https://doi.org/10.15672/hujms.573315

Abstract

References

  • [1] G.J. Chang and D. Kuo, The $L(2, 1)$-labelling problem on graphs, SIAM J. Discrete Math. 9, 309–316, 1996.
  • [2] G.J. Chang, C. Lu, and S. Zhou, Distance-two labellings of Hamming graphs, Discrete Appl. Math. 157, 1896–1904, 2009.
  • [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] 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] G. Chartrand, L. Nebesky, and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph. Theory, 24, 5–21, 2004.
  • [6] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
  • [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] J.R. Griggs and X.T. Jin, Real number graph labelling with distance conditions, SIAM J. Discrete Math. 20, 302–327, 2006.
  • [9] J.R. Griggs, and D. Král’, Graph labellings with variable weights, a survey, Discrete Appl. Math. 157, 2646–2658, 2009.
  • [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] W.K. Hale, Frequency assignment, theory and application, Proc. IEEE, 68, 1497– 1514, 1980.
  • [12] J.v.d. Heuvel, R. Leese, and M. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory, 29, 263–283, 1998.
  • [13] J.S.-T. Juan and D.D.-F. Liu, Antipodal labelings for cycles, Ars Combin. 103, 81–96, 2012.
  • [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] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
  • [16] R. Khennoufa and O. Togni, The radio antipodal and radio numbers of the hypercube, Ars Combin. 102, 447–461, 2011.
  • [17] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohem. 130 (3), 277–282, 2005.
  • [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] 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] D. Král’, The channel assignment problem with variable weights, SIAM J. Discrete Math. 20, 690–704, 2006.
  • [21] X. Li, V. Mak, and S. Zhou, Optimal radio labellings of complete m-ary trees, Discrete Appl. Math. 158, 507–515, 2010.
  • [22] D.D.-F. Liu, Radio number for trees, Discrete Math. 308, 1153–1164, 2008.
  • [23] D.D.-F. Liu and M. Xie, Radio number for square of cycles, Congr. Numer. 169, 105–125, 2004.
  • [24] D.D.-F. Liu and M. Xie, Radio number for square paths, Ars Combin. 90, 307–319, 2009.
  • [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] 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] 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] 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] L. Saha and P. Panigrahi, A graph Radio k-coloring algorithm, Lecture notes in Computer Science 7643, 125–129, 2012.
  • [30] L. Saha and P. Panigrahi, On the Radio number of Toroidal grids, Australian J. Combin. 55, 273–288, 2013.
  • [31] L. Saha and P. Panigrahi, A lower bound for radio k-chromatic number, Discrete Appl. Math. 192, 87–100, 2015.
  • [32] U. Sarkar and A. Adhikari, On characterizing radio k-coloring problem by path covering problem, Discrete Math 338 (4), 615–620, 2015.
  • [33] P. Zhang, Radio labellings of cycles, Ars Combin 65, 21–32, 2002.
  • [34] S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theoret. Comput. Sci. 310, 501–511, 2004.
  • [35] S. Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Discrete Math. 19, 985–1003, 2006.
  • [36] S. Zhou, A distance-labelling problem for hypercubes, Discrete Appl. Math. 156, 2846– 2854, 2008.

Radio $k$-labeling of paths

Year 2020, Volume: 49 Issue: 6, 1926 - 1943, 08.12.2020
https://doi.org/10.15672/hujms.573315

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

References

  • [1] G.J. Chang and D. Kuo, The $L(2, 1)$-labelling problem on graphs, SIAM J. Discrete Math. 9, 309–316, 1996.
  • [2] G.J. Chang, C. Lu, and S. Zhou, Distance-two labellings of Hamming graphs, Discrete Appl. Math. 157, 1896–1904, 2009.
  • [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] 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] G. Chartrand, L. Nebesky, and P. Zhang, Radio k-colorings of paths, Discuss. Math. Graph. Theory, 24, 5–21, 2004.
  • [6] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
  • [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] J.R. Griggs and X.T. Jin, Real number graph labelling with distance conditions, SIAM J. Discrete Math. 20, 302–327, 2006.
  • [9] J.R. Griggs, and D. Král’, Graph labellings with variable weights, a survey, Discrete Appl. Math. 157, 2646–2658, 2009.
  • [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] W.K. Hale, Frequency assignment, theory and application, Proc. IEEE, 68, 1497– 1514, 1980.
  • [12] J.v.d. Heuvel, R. Leese, and M. Shepherd, Graph labelling and radio channel assignment, J. Graph Theory, 29, 263–283, 1998.
  • [13] J.S.-T. Juan and D.D.-F. Liu, Antipodal labelings for cycles, Ars Combin. 103, 81–96, 2012.
  • [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] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33, 77–85, 2001.
  • [16] R. Khennoufa and O. Togni, The radio antipodal and radio numbers of the hypercube, Ars Combin. 102, 447–461, 2011.
  • [17] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohem. 130 (3), 277–282, 2005.
  • [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] 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] D. Král’, The channel assignment problem with variable weights, SIAM J. Discrete Math. 20, 690–704, 2006.
  • [21] X. Li, V. Mak, and S. Zhou, Optimal radio labellings of complete m-ary trees, Discrete Appl. Math. 158, 507–515, 2010.
  • [22] D.D.-F. Liu, Radio number for trees, Discrete Math. 308, 1153–1164, 2008.
  • [23] D.D.-F. Liu and M. Xie, Radio number for square of cycles, Congr. Numer. 169, 105–125, 2004.
  • [24] D.D.-F. Liu and M. Xie, Radio number for square paths, Ars Combin. 90, 307–319, 2009.
  • [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] 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] 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] 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] L. Saha and P. Panigrahi, A graph Radio k-coloring algorithm, Lecture notes in Computer Science 7643, 125–129, 2012.
  • [30] L. Saha and P. Panigrahi, On the Radio number of Toroidal grids, Australian J. Combin. 55, 273–288, 2013.
  • [31] L. Saha and P. Panigrahi, A lower bound for radio k-chromatic number, Discrete Appl. Math. 192, 87–100, 2015.
  • [32] U. Sarkar and A. Adhikari, On characterizing radio k-coloring problem by path covering problem, Discrete Math 338 (4), 615–620, 2015.
  • [33] P. Zhang, Radio labellings of cycles, Ars Combin 65, 21–32, 2002.
  • [34] S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theoret. Comput. Sci. 310, 501–511, 2004.
  • [35] S. Zhou, Labelling Cayley graphs on abelian groups, SIAM J. Discrete Math. 19, 985–1003, 2006.
  • [36] S. Zhou, A distance-labelling problem for hypercubes, Discrete Appl. Math. 156, 2846– 2854, 2008.
There are 36 citations in total.

Details

Primary Language English
Subjects Mathematical Sciences
Journal Section Mathematics
Authors

Laxman Saha This is me

Satyabrata Das This is me 0000-0002-4970-9470

Kinkar Chandra Das 0000-0003-2576-160X

Kalishankar Tiwary 0000-0002-5773-2021

Publication Date December 8, 2020
Published in Issue Year 2020 Volume: 49 Issue: 6

Cite

APA Saha, L., Das, S., Das, K. C., Tiwary, K. (2020). Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics, 49(6), 1926-1943. https://doi.org/10.15672/hujms.573315
AMA Saha L, Das S, Das KC, Tiwary K. Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics. December 2020;49(6):1926-1943. doi:10.15672/hujms.573315
Chicago Saha, Laxman, Satyabrata Das, Kinkar Chandra Das, and Kalishankar Tiwary. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics 49, no. 6 (December 2020): 1926-43. https://doi.org/10.15672/hujms.573315.
EndNote Saha L, Das S, Das KC, Tiwary K (December 1, 2020) Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics 49 6 1926–1943.
IEEE L. Saha, S. Das, K. C. Das, and K. Tiwary, “Radio $k$-labeling of paths”, Hacettepe Journal of Mathematics and Statistics, vol. 49, no. 6, pp. 1926–1943, 2020, doi: 10.15672/hujms.573315.
ISNAD Saha, Laxman et al. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics 49/6 (December 2020), 1926-1943. https://doi.org/10.15672/hujms.573315.
JAMA Saha L, Das S, Das KC, Tiwary K. Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics. 2020;49:1926–1943.
MLA Saha, Laxman et al. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics, vol. 49, no. 6, 2020, pp. 1926-43, doi:10.15672/hujms.573315.
Vancouver Saha L, Das S, Das KC, Tiwary K. Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics. 2020;49(6):1926-43.