Rainbow Connection Number Of Graph Power And Graph Products
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 G1 is an upper bound for rc(G)of any nontrivial graph G. For all nontrivial, bridgeless and connected graphs G, Basavaraju etal. Showed that rc(G) can be upperbounded 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 upperbound better than G  1 in the case of graphs with bridges. An immediate and natural question is the following: Are there classes of bridgeless 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 upperbounded by 2r(G)+c, where r(G) is radius of the resultant graph and c ε {0, 1, 2}.
Collections
Related items
Showing items related by title, author, creator and subject.

Rainbow Colouring and Some Dimensional Problems in Graph Theory
Rajendraprasad, Deepak (20180405)This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices ... 
A Modified SumProduct Algorithm over Graphs with Short Cycles
Raveendran, Nithin (20180718)We investigate into the limitations of the sumproduct algorithm for binary low density parity check (LDPC) codes having isolated short cycles. Independence assumption among messages passed, assumed reasonable in all ... 
Experimental Studies On A New Class Of Combinatorial LDPC Codes
Dang, Rajdeep Singh (20090605)We implement a package for the construction of a new class of Low Density Parity Check (LDPC) codes based on a new random high girth graph construction technique, and study the performance of the codes so constructed on ...