Rainbow connection number and connected dominating sets

DOI10.1002/JGT.20643zbMATH Open1248.05098arXiv1010.2296OpenAlexW1535932596MaRDI QIDQ2911064FDOQ2911064

Authors: L. Sunil Chandran, Anita Das, Deepak Rajendraprasad, Nithin M. Varma 

Publication date: 12 September 2012

Published in: Journal of Graph Theory (Search for Journal in Brave)

Abstract: 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, the rainbow connection number is upper bounded by {gamma}_c(G) + 2, where {gamma}_c(G) is the connected domination number of G. Bounds of the form diameter(G) leq rc(G) leq diameter(G) + c, 1 leq c leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G) leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. 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 {delta}, the rainbow connection number is upper bounded by 3n/({delta} + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20n/{delta} by Krivelevich and Yuster (2010). Moreover, this bound is seen to be tight up to additive factors by a construction of Caro et al. (2008).

Full work available at URL: https://arxiv.org/abs/1010.2296

Recommendations

• Rainbow connection number and connected dominating sets
• Rainbow connection and minimum degree
• On rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Note on the upper bound of the rainbow index of a graph

zbMATH Keywords

minimum degreeradiusrainbow connectivityconnected dominating setrainbow coloringconnected two-step dominating set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cites Work

• On rainbow connection
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The Complexity of the Partial Order Dimension Problem
• Asteroidal Triple-Free Graphs
• Hardness and Algorithms for Rainbow Connectivity
• Chromatic graph theory

Cited In (48)

• The \((k,\ell)\)-rainbow index of random graphs
• The 3-rainbow index and connected dominating sets
• Generalized rainbow connection of graphs
• Rainbow connection numbers of Cayley graphs
• Linear separation of connected dominating sets in graphs
• Upper bound involving parameter \(\sigma_2\) for the rainbow connection number
• Rainbow connection numbers of Cayley digraphs on abelian groups
• Rainbow connection in 3-connected graphs
• Rainbow connection number, bridges and radius
• Proper rainbow connection number of graphs
• Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs
• Upper bounds of proper connection number of graphs
• Finite families of forbidden subgraphs for rainbow connection in graphs
• Note on the upper bound of the rainbow index of a graph
• Some results on the total proper \(k\)-connection number
• Some results on the 3-total-rainbow index
• Upper bounding rainbow connection number by forest number
• Nordhaus-Gaddum-type theorem for rainbow connection number of graphs
• Rainbow connection number and radius
• Rainbow Connection Numbers for Undirected Double-Loop Networks
• Generalized rainbow connectivity of graphs
• Upper bounds for the total rainbow connection of graphs
• Note on the hardness of rainbow connections for planar and line graphs
• Rainbow connection of random regular graphs
• Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2
• Rainbow connection numbers and the minimum degree sum of a graph
• Some results on the 3-vertex-rainbow index of a graph
• Rainbow connection for some families of hypergraphs
• The vertex-rainbow connection number of some graph operations
• Rainbow connection number and independence number of a graph
• Rainbow colouring of split graphs
• On forbidden subgraphs and rainbow connection in graphs with minimum degree 2
• Odd connection and odd vertex-connection of graphs
• Rainbow connection number of graph power and graph products
• Rainbow connection number and the number of blocks
• Concentration of rainbow \(k\)-connectivity of a multiplex random graph
• Rainbow connection and forbidden subgraphs
• Rainbow connection number and connected dominating sets
• Rainbow connection number of corona product of graphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Algorithms for the rainbow vertex coloring problem on graph classes
• Rainbow vertex-connection number on a small-world Farey graph
• Rainbow and monochromatic vertex-connection of random graphs
• Proper connection numbers of complementary graphs
• Algorithm on rainbow connection for maximal outerplanar graphs
• Loose edge-connection of graphs
• Total rainbow connection numbers of some special graphs
• Proper connection number and connected dominating sets

This page was built for publication: Rainbow connection number and connected dominating sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2911064)