We studied radio labelings of graphs in response to the Channel Assignment Problem (CAP). In a graph $ G, $ the radio labeling is a mapping $ \varpi:V(G) \rightarrow \{0, 1, 2, ..., \}, $ such as $ |\varpi(\mu')-\varpi(\mu'')|\geq diam(G)+1-d(\mu', \mu''). $ The label of $ \mu $ for under $ \varpi $ is defined by the integer $ \varpi(\mu), $ and the span under is defined by $ span(\varpi) = max \{|\varpi(\mu')-\varpi(\mu'')|: \mu', \mu'' \in V(G)\}. $ $ rn(G) = min_{\varpi} span(\varpi) $ is defined as the radio number of $ G $ when the minimum over all radio labeling $ \varpi $ of $ G $ is taken. $ G $ is said to be optimal if its radio labeling is $ span(\varpi) = rn(G). $ A graph H is said to be an $ m $ super subdivision if $ G $ is replaced by the complete bipartite graph $ K_{m, m} $ with $ m = 2 $ in such a way that the end vertices of the edge are merged with any two vertices of the same partite set $ X $ or $ Y $ of $ K_{m, m} $ after removal of the edge of $ G $. Up to this point, many lower and upper bounds of $ rn(G) $ have been found for several kinds of graph families. This work presents a comprehensive analysis of the radio number $ rn(G) $ for a graph $ G $, with particular emphasis on the $ m $ super subdivision of a path $ P_{n} $ with $ n (n \geq 3) $ vertices, along with a complete bipartite graph $ K_{m, m} $ consisting of $ m $ v/ertices, where $ m = 2 $.
Citation: Baskar Mari, Ravi Sankar Jeyaraj. Radio number of $ 2- $ super subdivision for path related graphs[J]. AIMS Mathematics, 2024, 9(4): 8214-8229. doi: 10.3934/math.2024399
We studied radio labelings of graphs in response to the Channel Assignment Problem (CAP). In a graph $ G, $ the radio labeling is a mapping $ \varpi:V(G) \rightarrow \{0, 1, 2, ..., \}, $ such as $ |\varpi(\mu')-\varpi(\mu'')|\geq diam(G)+1-d(\mu', \mu''). $ The label of $ \mu $ for under $ \varpi $ is defined by the integer $ \varpi(\mu), $ and the span under is defined by $ span(\varpi) = max \{|\varpi(\mu')-\varpi(\mu'')|: \mu', \mu'' \in V(G)\}. $ $ rn(G) = min_{\varpi} span(\varpi) $ is defined as the radio number of $ G $ when the minimum over all radio labeling $ \varpi $ of $ G $ is taken. $ G $ is said to be optimal if its radio labeling is $ span(\varpi) = rn(G). $ A graph H is said to be an $ m $ super subdivision if $ G $ is replaced by the complete bipartite graph $ K_{m, m} $ with $ m = 2 $ in such a way that the end vertices of the edge are merged with any two vertices of the same partite set $ X $ or $ Y $ of $ K_{m, m} $ after removal of the edge of $ G $. Up to this point, many lower and upper bounds of $ rn(G) $ have been found for several kinds of graph families. This work presents a comprehensive analysis of the radio number $ rn(G) $ for a graph $ G $, with particular emphasis on the $ m $ super subdivision of a path $ P_{n} $ with $ n (n \geq 3) $ vertices, along with a complete bipartite graph $ K_{m, m} $ consisting of $ m $ v/ertices, where $ m = 2 $.
| [1] | A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), 1967. |
| [2] | M. R. Z. El Deen, G. Elmahdy, New classes of graphs with edge $\delta-$ graceful labeling, AIMS Math., 7 (2022), 3554–3589. |
| [3] | A. Semaničová-Feňovčíková, A. N. Koam, A. Ahmad, M. Bača, A. Semaničová-Feňovčíková, Modular edge irregularity strength of graphs, AIMS Math., 8 (2023), 1475–1487. |
| [4] |
K. K. Yoong, R. Hasni, G. C. Lau, M. A. Asim, A. Ahmad, Reflexive edge strength of convex polytopes and corona product of cycle with path, AIMS Math., 7 (2022), 11784–11800. https://doi.org/10.3934/math.2022657 doi: 10.3934/math.2022657
|
| [5] |
D. D. F. Liu, X. Zhu, Multilevel distance labelings for paths and cycles, SIAM J. Discrete Math., 19 (2005), 610–621. https://doi.org/10.1137/S0895480102417768 doi: 10.1137/S0895480102417768
|
| [6] |
W. K. Hale, Frequency assignment: Theory and applications, P. IEEE, 68 (1980), 1497–1514. 10.1109/PROC.1980.11899 doi: 10.1109/PROC.1980.11899
|
| [7] | G. Chartrand, D. Erwin, Radio labelings of graphs, 2001. |
| [8] |
G. Chartrand, D. Erwin, P. Zhang, A graph labeling problem suggested by FM channel restrictions, Bull. Inst. Combin. Appl., 43 (2005), 43–57. https://doi.org/10.1081/CLT-200045053 doi: 10.1081/CLT-200045053
|
| [9] |
D. Bantva, D. D. Liu, Optimal radio labellings of block graphs and line graphs of trees, Theor. Comput. Sci., 891 (2021), 90–104. https://doi.org/10.1016/j.tcs.2021.06.034 doi: 10.1016/j.tcs.2021.06.034
|
| [10] |
S. Zhou, A channel assignment problem for optical networks modelled by Cayley graphs, Theor. Comput. Sci., 310 (2004), 501–511. https://doi.org/10.1016/S0304-3975(03)00394-3 doi: 10.1016/S0304-3975(03)00394-3
|
| [11] | D. Bantva, D. D. Liu, Radio number for the cartesian product of two trees, arXiv preprint arXiv: 2202.13983, 2022. |
| [12] | G. Sethuraman, P. Selvaraju, Gracefulness of arbitrary supersubdivisions of graphs, Indian J. Pure Appl. Math., 32 (2001), 1059–1064. |
| [13] |
D. D. Liu, M. Xie, Radio number for square paths, Ars. Combin., 90 (2009), 307–319. https://doi.org/10.4414/saez.2009.14172 doi: 10.4414/saez.2009.14172
|
| [14] | B. Sooryanarayana, M. V. Kumar, K. Manjula, Radio number of cube of a path, Int. J. Math. Comb, 1 (2010), 5–29. |
| [15] | C. H. Jung, W. Nazeer, S. Nazeer, A. Rafiq, Radio number for cross product Pn (P2), Int. J. Pure Appl. Math., 97 (2014), 515–525. |
| [16] | S. Nazeer, I. Kousar, RADIO LABELINGS FOR CORONA PRODUCT OF $P_2 \bigodot W_n, n \geq 6$, Int. J. Pure Apll. Math., 95 (2014), 0–8. |
| [17] | B. M. Kim, W. Hwang, B. C. Song, Radio number for the product of a path and a complete graph, J. Comb. Optim., 30 (2015), 139–149. |
| [18] | D. Bantva, A lower bound for the radio number of graphs, Conference on algorithms and discrete applied mathematics, (2019), 161–173. |
| [19] |
H. Qi, S. Nazeer, I. Kousar, M. A. Umar. N. A. Shah, Radio labeling for strong product ${K_{3} \boxtimes P_{n}}$, IEEE Access, 8 (2020), 109801–109806. https://doi.org/10.1109/ACCESS.2020.3002397 doi: 10.1109/ACCESS.2020.3002397
|
| [20] | P. Vasoya, D. Bantva, Optimal radio labelings of the Cartesian product of the generalized Peterson graph and tree, arXiv preprint arXiv: 2304.10094, (2023). |
| [21] |
D. D. Liu, M. Xie, Radio number for square of cycles, Congr. Numer, 169 (2004), 105–125. https://doi.org/10.3917/comm.105.0125 doi: 10.3917/comm.105.0125
|
| [22] |
D. D. Liu, Radio number for trees, Discrete Math., 308 (2008), 1153–1164. https://doi.org/10.1016/j.disc.2007.03.066 doi: 10.1016/j.disc.2007.03.066
|
| [23] | C. Fernandez, T. Flores, M. Tomova, C. Wyels, The radio number of gear graphs, arXiv preprint arXiv: 0809.2623, (2008). |
| [24] |
D. Bantva, Radio number for middle graph of paths, Electronic Notes Discrete Math., 63 (2017), 93–100. https://doi.org/10.1016/j.endm.2017.11.003 doi: 10.1016/j.endm.2017.11.003
|
| [25] |
F. Harary, Graph theory Reading, Massachusetts, Addison-Wesley, 274 (1972), 56–59. https://doi.org/10.2307/3617830 doi: 10.2307/3617830
|
| [26] | J. A. Gallian, A dynamic survey of graph labeling, Electron. J. comb., 1 (2018), DS6. |
| [27] | V. Srinivasan, N. Chidambaram, N. Devadoss, R. Pakkirisamy, P. Krishnamoorthi, On the gracefulness of m-super subdivision of graphs, J. Discret. Math. Sci. C., 23 (2020), 1359–1368. |
Figures(7) / Tables(2)
Baskar Mari, Ravi Sankar Jeyaraj. Radio number of $ 2- $ super subdivision for path related graphs[J]. AIMS Mathematics, 2024, 9(4): 8214-8229. doi: 10.3934/math.2024399
DownLoad: