Get all the updates for this publication
Rainbow Connection Number and Connected Dominating Sets
Rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, , where is the connected domination number of G. Bounds of the form , for many special graph classes follow as easy corollaries from this result. We also show that every bridge-less chordal graph G has . An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree . This solves an open problem from Schiermeyer, 2009 [Schiermeyer, I.
Journal | Electronic Notes in Discrete Mathematics |
---|---|
Open Access | No |