Radio Graceful Hamming Graphs

Niedzialomski, Amanda

Discussiones Mathematicae. Graph Theory, Tome 36 (2016) no. 4, pp. 1007-1020.

Résumé

For k ∈ℤ_+ and G a simple, connected graph, a k-radio labeling f : V (G) →ℤ_+ of G requires all pairs of distinct vertices u and v to satisfy |f(u) − f(v)| ≥ k + 1 − d(u, v). We consider k-radio labelings of G when k = diam (G). In this setting, f is injective; if f is also surjective onto 1, 2, . . ., |V (G)|, then f is a consecutive radio labeling. Graphs that can be labeled with such a labeling are called radio graceful. In this paper, we give two results on the existence of radio graceful Hamming graphs. The main result shows that the Cartesian product of t copies of a complete graph is radio graceful for certain t. Graphs of this form provide infinitely many examples of radio graceful graphs of arbitrary diameter. We also show that these graphs are not radio graceful for large t.

Détail

Keywords: radio labeling, radio graceful graph, Hamming graph

Bibliographie

[1] K.F. Benson, M. Porter and M. Tomova, The radio numbers of all graphs of order n and diameter n − 2, Matematiche (Catania) 68 (2013) 167-190.

[2] G. Chartrand, D. Erwin, P. Zhang and F. Harary, Radio labelings of graphs, Bull. Inst. Combin. Appl. 33 (2001) 77-85.

[3] G. Chartrand and P. Zhang, Radio colorings of graphs-a survey, Int. J. Comput. Appl. Math. 2 (2007) 237-252.

[4] C. Fernandez, A. Flores, M. Tomova and C.Wyles, The radio number of gear graphs, arXiv:0809.2623.

[5] J. Fiala, J. Kratochvíl and A. Proskurowski, Distance constrained labeling of precolored trees, Theoretical Computer Science, Torino, 2001, Lecture Notes in Comput. Sci. (Springer, Berlin, 2001) 285-292. doi: 10.1007/3-540-45446-2 18

[6] P.C. Fishburn and F.S. Roberts, No-hole L(2, 1)-colorings, Discrete Appl. Math. 130 (2003) 513-519. doi: 10.1016/S0166-218X(03)00329-9

[7] P.C. Fishburn and F.S. Roberts, Full color theorems for L(2, 1)-colorings, SIAM J. Discrete Math. 20 (2006) 428-443. doi: 10.1137/S0895480100378562

[8] J.R. Griggs and R.K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete Math. 5 (1992) 586-595. doi: 10.1137/0405048

[9] W.K. Hale, Frequency assignment: theory and applications, in: Proceedings of the IEEE 68 (1980) 1497-1514. doi: 10.1109/PROC.1980.11899

[10] X. Li, V.Mak and S. Zhou, Optimal radio labellings of complete m-ary trees, Discrete Appl. Math. 158 (2010) 507-515. doi: 10.1016/j.dam.2009.11.014

[11] D. D.-F. Liu, Radio number for trees, Discrete Math. 308 (2008) 1153-1164. doi: 10.1016/j.disc.2007.03.066

[12] D.D.-F. Liu and M. Xie, Radio number for square of cycles, in: Proceedings of the Thirty-Fifth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 169 (2004) 101-125.

[13] D.D.-F. Liu and X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math. 19 (2005) 610-621. doi: 10.1137/S0895480102417768

[14] P. Martinez, J. Ortiz, M. Tomova and C. Wyels, Radio numbers for generalized prism graphs, Discuss. Math. Graph Theory 31 (2011) 45-62. doi: 10.7151/dmgt.1529

[15] M. Morris-Rivera, M. Tomova, C. Wyels and A. Yeager, The radio number of Cn_Cn, Ars Combin. 120 (2015) 7-21.

[16] L. Saha and P. Panigrahi, Antipodal number of some powers of cycles, Discrete Math. 312 (2012) 1550-1557. doi: 10.1016/j.disc.2011.10.032

[17] L. Saha and P. Panigrahi, On the radio number of toroidal grids, Australas. J. Combin. 55 (2013) 273-288.

[18] L. Saha and P. Panigrahi, A lower bound for radio k-chromatic number, Discrete Appl. Math. 192 (2015) 87-100. doi: 10.1016/j.dam.2014.05.004

[19] B. Sooryanarayana and P. Raghunath, Radio labeling of cube of a cycle, Far East J. Appl. Math. 29 (2007) 113-147.

[20] R. Sweetly and J.P. Joseph, The radio number of (Wn : 2) graphs, J. Discrete Math. Sci. Cryptogr. 12 (2009) 729-736. doi: 10.1080/09720529.2009.10698268

[21] R.K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Math. 306 (2006) 1217-1231. doi: 10.1016/j.disc.2005.11.029