Regresar

Rainbow 2-connectivity of edge-comb product of a cycle and a Hamiltonian graph

Abstract:

An edge-colored graph G is rainbow k-connected, if for every two vertices of G, there are k internally disjoint rainbow paths, i.e., if no two edges of each path are colored the same. The minimum number of colors needed for which there exists a rainbow k-connected coloring of G, rck(G) , is the rainbow k-connection number of G. Let G and H be two connected graphs, where O is an orientation of G. Let e→ be an oriented edge of H. The edge-comb product of G (under the orientation O) and H on e→ , Go⊳ e→H, is a graph obtained by taking one copy of G and |E(G)| copies of H and identifying the i-th copy of H at the edge e→ to the i-th edge of G, where the two edges have the same orientation. In this paper, we provide sharp lower and upper bounds for rainbow 2-connection numbers of edge-comb product of a cycle and a Hamiltonian graph. We also determine the rainbow 2-connection numbers of edge-comb product of a cycle with some graphs, i.e. complete graph, fan graph, cycle graph, and wheel graph.