Rainbow Coloring of Cycle of Generalized Cycle and Wheel Graphs for Secured Communication Networks

Abstract

Connectivity is a central concept in graph theory, often used to model relationships and communication in networks. A recent and intriguing variation is rainbow connectivity. It involves assigning colors to the edges of a graph so that every pair of vertices is connected by a path in which all edges have distinct colors, known as a rainbow path. This concept has applications in secure communication networks, where messages must travel across diverse, non-repeating routes. In this work, we examine the rainbow connectivity of two important families of graphs: generalized cycle graphs and wheel graphs. These structures are commonly found in both theoretical graph studies and real-world networks. We determine the optimal edge-colorings that ensure rainbow connectivity in these graphs and establish their corresponding rainbow connection numbers. Our results provide insight into how structural properties of graphs influence their connectivity under rainbow constraints, contributing to the broader study of graph coloring and network design.

Keywords

Diameter / Rainbow connection number / Edge-coloring / Cycle graph / 05C15

References

[1] Arputhamarya A, Mercy MH. Rainbow coloring of shadow graphs. Int. J. Pure Appl. Math., 2015, 101(6): 873-881

[2] Chandran, L.S., Rajendraprasad, D.: Rainbow colouring of split and threshold graphs. In: Gudmundsson, J., Mestre, J., Viglas, T. (eds) Computing and Combinatorics. COCOON 2012. Lecture Notes in Computer Science, vol. 7434, pp. 181–192. Springer, Berlin, Heidelberg (2012)

[3] Chartrand G, Johns GL, McKeon KA, Ping Z. Rainbow connection in graphs. Math. Bohem., 2008, 133: 85-98

[4] Fredlina KQ, Salman ANM, Julihara IGPK, Werthi KT, Putri NLPNS. Rainbow coloring of three new graph classes. In. J. Phys.: Conf. Ser., 2021, 1783(1): 012033

[5] Jeyanthi P, Jeya Daisy K. Z_k-magic labeling of cycle of graph. Int. J. Math. Combin., 2019, 1: 88-102

[6] Li X, Shi Y, Sun Y. Rainbow connection of graphs: a survey. Graphs Combin., 2013, 29(1): 1-38

[7] Li X, Sun Y. Rainbow Connections of Graphs, 2012, New York, NY, USA. Springer Science+Business Media

[8] Ma X, Feng M, Wang K. The rainbow connection number of the power graph of a finite group. Graphs Combin, 2016, 32: 1495-1504

[9] Rao KS, Murali R. Rainbow critical graphs. Int. J. Comp. Appl, 2014, 4(4): 252-259

[10] Rao KS, Murali R. Rainbow connection number in the brick product graphs C(2n, m, r). Int. J. Math. Combin., 2017, 2: 70-83

[11] Rao KS, Murali R, Rajendra SK. Rainbow and strong rainbow criticalness of some standard graphs. Int. J. Mathemat. Comput. Res., 2015, 3(1): 829-836

[12] Rao KS, Murali R, Rajendra SK. Rainbow connection number in the brick product graphs. Bull. Int. Math. Virtual Inst., 2018, 8: 55-66

[13] Restry D, Salman ANM. The rainbow connection number of an n-crossed prism graph and its coroners product with a trivial graph. Procedia Comput. Sci., 2015, 74: 143-150

[14] Schiermeyer I. Bounds for the rainbow connection number of graphs. Discuss. Math. Graph Theory, 2011, 31(2): 387-395

[15] Sun YGao D, Ruan N, Xing W. Rainbow connection numbers for undirected double-loop networks. Advances in Global Optimization, 2015, Cham. Springer: 109-116 95

[16] Sy S, Wijaya R, Surahmat. Rainbow connection number of some graphs. Appl. Math. Sci., 2014, 8(94): 4693-4696

RIGHTS & PERMISSIONS

Shanghai University