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

DOI10.1007/S00373-012-1183-XMaRDI QIDQ367076zbMATH OpenOpenAlexFDO

Authors Lily Chen, Xueliang Li, Huishu Lian

Publication date 26 September 2013

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

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

zbMATH Keywords

edge-colored graphNordhaus-Gaddum-typerainbow connection number

Mathematics Subject Classification ID

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

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.

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; zbMATH DE number 6837036
• Rainbow connection in 3-connected graphs

Cites work

• scientific article; zbMATH DE number 5015716 (Why is no real title available?)
• Graph theory
• Nordhaus-Gaddum inequalities for domination in graphs
• On Complementary Graphs
• Rainbow connection in graphs
• Rainbow connection number and connected dominating sets
• The Diameter of a Graph and its Complement

Cited in

(11)

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

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)