Antipodal Number of Cartesian Product of Complete Graphs with Cycles

Document Type : Original paper

Authors

Department of Mathematics, Indian Institute of Technology Kharagpur

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

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 $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.
https://doi.org/10.1109/INDCON.2011.6139450
[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.
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 15 October 2023

Files

Share

How to cite

Statistics