Show simple item record

dc.contributor.advisorChandran, L Sunil
dc.contributor.authorArunselvan, R
dc.date.accessioned2014-09-09T09:54:14Z
dc.date.accessioned2018-07-31T04:38:28Z
dc.date.available2014-09-09T09:54:14Z
dc.date.available2018-07-31T04:38:28Z
dc.date.issued2014-09-09
dc.date.submitted2011
dc.identifier.urihttps://etd.iisc.ac.in/handle/2005/2383
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/3066/G25301-Abs.pdfen_US
dc.description.abstractThe 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.isoen_USen_US
dc.relation.ispartofseriesG25301en_US
dc.subjectGraph Theoryen_US
dc.subjectRainbow Connection Numberen_US
dc.subjectGraph Coloringen_US
dc.subjectGraph Product Operationsen_US
dc.subjectGraph Powering Operationen_US
dc.subjectCartesian Product (Graphs)en_US
dc.subjectLexicographic Product (Graphs)en_US
dc.subjectStrong Product (Graphs)en_US
dc.subjectRainbow Coloring (Graphs)en_US
dc.subjectConnected Graphen_US
dc.subjectCartesian Producten_US
dc.subject.classificationComputer Scienceen_US
dc.titleRainbow Connection Number Of Graph Power And Graph Productsen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record