International Journal of Mathematics And Computer Research

Abstract

A path in an edge−colored graph is said to be a rainbow path,if every edge in the path has different color. An edge colored graph is rainbow connected if there exists a rainbow path between every pair of vertices. The rainbow connection of a graph G, denoted by rcG , is the smallest number of colors required to color the edges of graph such that the graph is rainbow connected. Given two arbitrary vertices u and v in G, a  rainbow u  v geodesic in G is a rainbow u  v path of length d(u, v), where d(u, v) is the distance between u and v. The graph G is strongly rainbow connected if there exists a rainbow u  v geodesic for any two vertices u and v in G. The strong rainbow connection number of G, denoted by srcG , is the minimum number of colors needed to make G strongly rainbow connected. Deletion of any edge in G if the property alters, then that graph is called critical graph with respect to that property. In this paper we find the rainbow connection number of Cartesian product of pan graph, Stacked Book Graph, their criticalness with respect to rainbow coloring and strong rainbow connection of Book graph.