Nordhaus-Gaddum-type theorem for rainbow connection number of graphs

DOI10.1007/S00373-012-1183-XzbMATH Open1272.05044arXiv1012.2641OpenAlexW2000391936MaRDI QIDQ367076FDOQ367076

Authors: Lily Chen, Xueliang Li, Huishu Lian 

Publication date: 26 September 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: An edge-colored graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of $G$, denoted $rc(G)$, is the minimum number of colors that are used to make $G$ rainbow connected. In this paper we give a Nordhaus-Gaddum-type result for the rainbow connection number. We prove that if $G$ and $$ are both connected, then $$. Examples are given to show that the upper bound is sharp for all $ngeq4$, and the lower bound is sharp for all $ngeq8$. For the rest small $n=4,5,6,7,$ we also give the sharp bounds.

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

Recommendations

• Nordhaus-Gaddum-type bounds for the rainbow vertex-connection number of a graph
• Generalized rainbow connection of graphs and their complements
• Rainbow connection number of dense graphs
• scientific article
• Rainbow connection in 3-connected graphs

zbMATH Keywords

edge-colored graphNordhaus-Gaddum-typerainbow connection number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• Graph theory
• Rainbow connections of graphs
• Rainbow connection number and connected dominating sets
• Rainbow connection in graphs
• On Complementary Graphs
• Title not available (Why is that?)
• Nordhaus-Gaddum inequalities for domination in graphs
• The Diameter of a Graph and its Complement

Cited In (12)

• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• The vertex-rainbow index of a graph
• More on the rainbow disconnection in graphs
• The rainbow vertex-index of complementary graphs
• Rainbow connections of graphs
• Total rainbow connection number and complementary graph
• Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings
• On conflict-free connection of graphs
• Tight Nordhaus-Gaddum-type upper bound for total-rainbow connection number of graphs
• Proper connection numbers of complementary graphs
• The (vertex-)monochromatic index of a graph
• Nordhaus-Gaddum-type bounds for the rainbow vertex-connection number of a graph

This page was built for publication: Nordhaus-Gaddum-type theorem for rainbow connection number of graphs

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