Mathematics – Combinatorics
Scientific paper
2011-04-21
Mathematics
Combinatorics
15 pages. This is a revised (journal-ready) version
Scientific paper
Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (Note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely cartesian product, lexicographic product and strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) <= 2r(G)+c, where r(G) denotes the radius of G and c \in {0,1,2}. In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [Basavaraju et. al, 2010]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight upto additive constants. The proofs are constructive and hence yield polynomial time (2 + 2/r(G))-factor approximation algorithms.
Basavaraju Manu
Chandran Sunil L.
Rajendraprasad Deepak
Ramaswamy Arunselvan
No associations
LandOfFree
Rainbow Connection Number of Graph Power and Graph Products does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Rainbow Connection Number of Graph Power and Graph Products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rainbow Connection Number of Graph Power and Graph Products will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-177947