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\in [1,d]$ be an integer. A radio $k$-coloring of graph $G$ is a mapping $g:V(G)\rightarrow \{0\}\cup \mathbb{N}$ satisfying $\lvert g(u)-g(v)\rvert\geq 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 ${\text{max}} \{g(u):u\in V(G)\}$ is known as the span of $g$ and is denoted by $rc_k(g)$. The radio $k$-chromatic number of graph $G$, denoted by $rc_k(G)$, is defined as $\text{min} \{rc_k(g) : g \text{ is a radio $k$-coloring of $G$}\}$. For $k=d-1$, the radio $k$-coloring of graph $G$ is called an antipodal coloring. So $rc_{d-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 $K_r$ and cycle $C_s$, $K_r\square C_s$, for $r\geq 4$ and $s\geq 3$. We determine the antipodal number of $K_r\square C_s$, for even $r\geq 4$ with $s\equiv 1(mod\,4)$; and for any $r\geq 4$ with $s=4t+2$, $t$ odd. Also, for the remaining values of $r$ and $s$, we give lower and upper bounds for $ac(K_r\square C_s)$.

Keywords

Main Subjects


[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 $Q_n$, 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 $C_n\Box C_n$, 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.