Araştırma Makalesi
BibTex RIS Kaynak Göster

Yıl 2020, Cilt: 49 Sayı: 6, 1926 - 1943, 08.12.2020

Laxman Saha Satyabrata Das Kinkar Chandra Das Kalishankar Tiwary

https://doi.org/10.15672/hujms.573315
Cited By: 2

Öz

Kaynakça

  • [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

Yıl 2020, Cilt: 49 Sayı: 6, 1926 - 1943, 08.12.2020

Laxman Saha Satyabrata Das Kinkar Chandra Das Kalishankar Tiwary

https://doi.org/10.15672/hujms.573315
Cited By: 2

Öz

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

Anahtar Kelimeler

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

Kaynakça

  • [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.
Toplam 36 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Konular Matematik
Bölüm Matematik
Yazarlar

Laxman Saha Bu kişi benim

Satyabrata Das Bu kişi benim 0000-0002-4970-9470

Kinkar Chandra Das 0000-0003-2576-160X

Kalishankar Tiwary 0000-0002-5773-2021

Yayımlanma Tarihi 8 Aralık 2020
Yayımlandığı Sayı Yıl 2020 Cilt: 49 Sayı: 6

Kaynak Göster

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. Aralık 2020;49(6):1926-1943. doi:10.15672/hujms.573315
Chicago Saha, Laxman, Satyabrata Das, Kinkar Chandra Das, ve Kalishankar Tiwary. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics 49, sy. 6 (Aralık 2020): 1926-43. https://doi.org/10.15672/hujms.573315.
EndNote Saha L, Das S, Das KC, Tiwary K (01 Aralık 2020) Radio $k$-labeling of paths. Hacettepe Journal of Mathematics and Statistics 49 6 1926–1943.
IEEE L. Saha, S. Das, K. C. Das, ve K. Tiwary, “Radio $k$-labeling of paths”, Hacettepe Journal of Mathematics and Statistics, c. 49, sy. 6, ss. 1926–1943, 2020, doi: 10.15672/hujms.573315.
ISNAD Saha, Laxman vd. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics 49/6 (Aralık 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 vd. “Radio $k$-Labeling of Paths”. Hacettepe Journal of Mathematics and Statistics, c. 49, sy. 6, 2020, ss. 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.

Cited By

Radio k-chromatic Number of Full m-ary Trees
Theory of Computing Systems
https://doi.org/10.1007/s00224-021-10056-7
Relationship between radio k-chromatic number of graphs and square graphs
AKCE International Journal of Graphs and Combinatorics
https://doi.org/10.1080/09728600.2021.1993730

https://dergipark.org.tr/en/pub/hujms