The rainbow 2-connectivity of Cartesian products of2-connected graphs and paths

Electronic Journal of Graph Theory and Applications

A.N.M. Salman¹  Rinovia Simanjuntak¹  Bety Hayat Susanti² 

[1] Combinatorial Mathematics Research Group,Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung;Sekolah Tinggi Sandi Negara;

关键词: cartesian product,2-connected graph, rainbow $2$-connectivity, rainbow path;   

DOI  :  10.5614/ejgta.2020.8.1.11

来源: DOAJ

【 摘 要 】

An edge-colored graph G is rainbow k-connected, if there are k-internally disjoint rainbow paths connecting every pair of vertices of G. The rainbow k-connection number of G, denoted by rc_k(G), is the minimum number of colors needed for which there exists a rainbow k-connected coloring for G. In this paper, we are able to find sharp lower and upper bounds for the rainbow 2-connection number of Cartesian products of arbitrary 2-connected graphs and paths. We also determine the rainbow 2-connection number of the Cartesian products of some graphs, i.e. complete graphs, fans, wheels, and cycles, with paths.

【 授权许可】

Unknown