dc.contributor.advisor Chandran, Sunil L dc.contributor.author Arunselvan, R dc.date.accessioned 2014-09-09T09:54:14Z dc.date.accessioned 2018-07-31T04:38:28Z dc.date.available 2014-09-09T09:54:14Z dc.date.available 2018-07-31T04:38:28Z dc.date.issued 2014-09-09 dc.date.submitted 2011 dc.identifier.uri https://etd.iisc.ac.in/handle/2005/2383 dc.identifier.abstract http://etd.iisc.ac.in/static/etd/abstracts/3066/G25301-Abs.pdf en_US dc.description.abstract 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}. en_US dc.language.iso en_US en_US dc.relation.ispartofseries G25301 en_US dc.subject Graph Theory en_US dc.subject Rainbow Connection Number en_US dc.subject Graph Coloring en_US dc.subject Graph Product Operations en_US dc.subject Graph Powering Operation en_US dc.subject Cartesian Product (Graphs) en_US dc.subject Lexicographic Product (Graphs) en_US dc.subject Strong Product (Graphs) en_US dc.subject Rainbow Coloring (Graphs) en_US dc.subject Connected Graph en_US dc.subject Cartesian Product en_US dc.subject.classification Computer Science en_US dc.title Rainbow Connection Number Of Graph Power And Graph Products en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.discipline Faculty of Engineering en_US
﻿