Rainbow connection number and connected dominating sets

DOI10.1002/jgt.20643zbMath1248.05098arXiv1010.2296OpenAlexW1535932596MaRDI QIDQ2911064

Anita Das, Deepak Rajendraprasad, L. Sunil Chandran, Nithin Varma

Publication date: 12 September 2012

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

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

zbMATH Keywords

minimum degreeradiusconnected dominating setrainbow connectivityrainbow coloringconnected two-step dominating set

Mathematics Subject Classification ID

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

Related Items (46)

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

Cites Work

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

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