Rainbow Connection Number of Graph Powers and Graph Products

Sunil Chandran Leela
Indian Institute of Science, Bangalore, India.

Manu Basavaraju
Indian Institute of Science, Bangalore, India

Deepak Rajendraprasad
Indian Institute of Science, Bangalore, India

Arunselvan Ramaswamy
Indian Institute of Science, Bangalore, India.

PDF

Minisymposium: GRAPH PRODUCTS

Content: 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 the Cartesian product, the lexicographic product and the 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) \leq 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. 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 up to additive constants. The proofs are constructive and hence yield polynomial time $(2+2/r(G))$ -factor approximation algorithms.

Back to all abstracts