Abstract
Let G be a graph with diameter d and \(k\le d\) be a positive integer. A radio k-labelling of G is a function f that assigns to each vertex with a non-negative integer such that the following holds for all vertices u, v: \(|f(u)-f(v)| \ge k + 1 - d(u,v)\), where d(u, v) is the distance between u and v. The span of f is the absolute difference of the largest and smallest values in f(V). The radio number of G is the minimum span of a radio labelling admitted by G. In this article, we study radio \((d-1)\)-labelling problem for full binary trees.
Supported by National Board of Higher Mathematics (NBHM), India, with grants no. 2/48(22)/R & D II/4033, 2017.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bantva, D., Vaidya, S., Zhou, S.: Radio number of trees. Discrete Appl. Math. 317, 110–122 (2017)
Chartrand, G., Erwin, D., Harary, F., Zhang, P.: Radio labelings of graphs. Bull. Inst. Comb. Appl. 33, 77–85 (2001)
Chartrand, G., Erwin, D., Zhang, P.: A graph labeling problem suggested by FM channel restrictions. Bull. Inst. Comb. Appl. 43, 43–57 (2005)
Chartrand, G. Erwin, D., Zhang, P.: Radio antipodal colorings of cycles. In: 2000 Proceedings of the Thirty-First Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 144, pp. 129–141, Boca Raton (2000)
Hale, W.: Frequency assignment theory and application. Proc. IEEE 68(12), 1497–1514 (1980)
Juan, J.S.-T., Liu, D.D.-F.: Antipodal labelings for cycles. Ars Comb. 103, 81–96 (2012)
Liu, D.D.-F., Zhu, X.: Multi-level distance labelings for paths and cycles. SIAM J. Discrete Math. 19(3), 610–621 (2005)
Liu, D.D.-F.: Radio number for trees. Discrete Math. 308(7), 1153–1164 (2008)
Reddy Palagiri, V.S., Iyer, K.V.: Upper bounds on the radio number of some trees. Int. J. Pure Appl. Math. 71(2), 207–215 (2011)
Khennoufa, R., Togni, O.: The radio antipodal and radio numbers of the hypercube. Ars Comb. 102, 447–461 (2011)
Khennoufa, R., Togni, O.: A note on radio antipodal colourings of paths. Math. Bohem. 130(3), 277–282 (2005)
Saha, L., Panigrahi, P.: On the radio number of Toroidal grids. Aust. J. Combin. 55, 273–288 (2013)
Saha, L., Panigrahi, P.: A lower bound for radio \(k\)-chromatic number. Discrete Appl. Math. 192, 87–100 (2015)
Saha, L., Panigrahi, P.: A graph radio k-coloring algorithm. In: Arumugam, S., Smyth, W.F. (eds.) IWOCA 2012. LNCS, vol. 7643, pp. 125–129. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-35926-2_15
Sarkar, U., Adhikari, A.: On characterizing radio \(k\)-labelling problem by path covering problem. Discrete Math. 338(4), 615–620 (2015)
Das, S., Ghosh, S.C., Nandi, S., Sen, S.: A lower bound technique for radio \(k\)-labelling. Discrete Math. 340(5), 855–861 (2017)
Zhou, S.: A channel assignment problem for optical networks modelled by Cayley graphs. Theor. Comput. Sci. 310, 501–511 (2004)
Li, X., Mak, V., Zhou, S.: Optimal radio labellings of complete \(m\)-ary trees. Discrete Appl. Math. 158, 507–515 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Das, S., Saha, L., Tiwary, K. (2020). Antipodal Radio Labelling of Full Binary Trees. In: Zhang, Z., Li, W., Du, DZ. (eds) Algorithmic Aspects in Information and Management. AAIM 2020. Lecture Notes in Computer Science(), vol 12290. Springer, Cham. https://doi.org/10.1007/978-3-030-57602-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-030-57602-8_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-57601-1
Online ISBN: 978-3-030-57602-8
eBook Packages: Computer ScienceComputer Science (R0)