Record Details

Rainbow Connection Number Of Graph Power And Graph Products

Electronic Theses of Indian Institute of Science

View Archive Info
 
 
Field Value
 
Title Rainbow Connection Number Of Graph Power And Graph Products
 
Creator Arunselvan, R
 
Subject Graph Theory
Rainbow Connection Number
Graph Coloring
Graph Product Operations
Graph Powering Operation
Cartesian Product (Graphs)
Lexicographic Product (Graphs)
Strong Product (Graphs)
Rainbow Coloring (Graphs)
Connected Graph
Cartesian Product
Computer Science
 
Description The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. This graph parameter was introduced by Chartrand et al. in 2008. The problem has garnered considerable interest and several variants of the initial version have since been introduced. The rainbow connection number of a connected graph G is denoted by rc(G). It can be shown that the rainbow connection number of a tree on n vertices is n -1. Hence |G|-1 is an upper bound for rc(G)of any non-trivial graph G. For all non-trivial, bridge-less and connected graphs G, Basavaraju etal. Showed that rc(G) can be upper-bounded by a quadratic function of its radius. In addition they also proved the tightness of the bound. It is clear that we cannot hope to get an upper-bound better than |G| - 1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridge-less graphs whose rainbow connection numbers are linear functions of their radii? This question is of particular interest since the diameter is a trivial lower bound for rc(G). We answer in affirmative to the above question. In particular we studied three (graph) product operations (Cartesian, Lexicographic and Strong) and the graph powering operation. We were able to show that the rainbow connection number of the graph resulting from any of the above graph operations is upper-bounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.
 
Contributor Chandran, L Sunil
 
Date 2014-09-09T09:54:14Z
2014-09-09T09:54:14Z
2014-09-09
2011-11
 
Type Thesis
 
Identifier http://etd.iisc.ernet.in/handle/2005/2383
http://etd.ncsi.iisc.ernet.in/abstracts/3066/G25301-Abs.pdf
 
Language en_US
 
Relation G25301