Antipodal Number of Cartesian Product of Complete Graphs with Cycles

Document Type : Original paper

Authors

Department of Mathematics, Indian Institute of Technology, Kharagpur, 721302, West Bengal, India

Abstract

Let G be a simple connected graph with diameter d, and k∈[1,d] be an integer. A radio k-coloring of graph G is a mapping g:V(G)→{0}∪N satisfying |g(u)−g(v)|≥1+k−d(u,v) for any pair of distinct vertices u and v of the graph G, where d(u,v) denotes distance between vertices u and v in G. The number max{g(u):u∈V(G)} is known as the span of g and is denoted by rck(g). The radio k-chromatic number of graph G, denoted by rck(G), is defined as min{rck(g):g is a radio k-coloring of G}. For k=d−1, the radio k-coloring of graph G is called an antipodal coloring. So rcd−1(G) is called the antipodal number of G and is denoted by ac(G). Here, we study antipodal coloring of the Cartesian product of the complete graph Kr and cycle Cs, Kr◻Cs, for r≥4 and s≥3. We determine the antipodal number of Kr◻Cs, for even r≥4 with s≡1(mod4); and for any r≥4 with s=4t+2, t odd. Also, for the remaining values of r and s, we give lower and upper bounds for ac(Kr◻Cs).

Keywords

Main Subjects

References

[1] G. Chartrand, D. Erwin, F. Harary, and P. Zhang, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001), 77–85.
[2] G. Chartrand, D. Erwin, and P. Zhang, Radio antipodal colorings of graphs, Math. Bohem. 127 (2002), no. 1, 57–69. http://dx.doi.org/10.21136/MB.2002.133978
[3] W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68 (1980), no. 12, 1497–1514. https://doi.org/10.1109/PROC.1980.11899
[4] J.S. Juan and D.D. Liu, Antipodal labelings for cycles., Ars Combin. 103 (2012), 81–96.
[5] M. Kchikech, R. Khennoufa, and O. Togni, Radio k-labelings for Cartesian products of graphs, Discuss. Math. Graph Theory 28 (2008), no. 1, 165–178. https://doi.org/10.7151/dmgt.1399
[6] R. Khennoufa and O. Togni, A note on radio antipodal colourings of paths, Math. Bohem. 130 (2005), no. 3, 277–282. http://dx.doi.org/10.21136/MB.2005.134100
[7] R. Khennoufa and O. Togni, The radio antipodal and radio numbers of the hypercube., Ars Combin. 102 (2011), 447–461.
[8] B.M. Kim, W. Hwang, and B.C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim. 30 (2015), 139–149. https://doi.org/10.1007/s10878-013-9639-3
[9] S. R. Kola and P. Panigrahi, An improved lower bound for the radio k-chromatic number of the hypercube Qn, Comput. Math. Appl. 60 (2010), no. 7, 2131–2140. https://doi.org/10.1016/j.camwa.2010.07.058
[10] S. R. Kola and P. Panigrahi, Radio numbers of some classes of GP(n,1) and Cin(1,r), Annual IEEE India Conference, IEEE, 2011, pp. 1–6.
[11] S.R. Kola and P. Panigrahi, A lower bound for radio k-chromatic number of an arbitrary graph, Contrib. Discrete Math. 10 (2015), no. 2, 45–56. https://doi.org/10.11575/cdm.v10i2.62253
[12] D.D. Liu and X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005), no. 3, 610–621. https://doi.org/10.1137/S0895480102417768
[13] M. Morris-Rivera, M. Tomova, C. Wyels, and A. Yeager, The radio number of Cn◻Cn, Ars Combin. 120 (2015), 7–21.
[14] L. Saha and P. Panigrahi, Antipodal number of some powers of cycles, Discrete Math. 312 (2012), no. 9, 1550–1557. https://doi.org/10.1016/j.disc.2011.10.032
[15] L. Saha and P. Panigrahi, On the radio number of toroidal grids., Australas. J. Combin. 55 (2013), 273–288.
Communications in Combinatorics and Optimization
Volume 10, Issue 1
March 2025
Pages 219-231

Files

Share

How to cite

Statistics