Rainbow connection numbers of complementary graphs

MaRDI QIDQ2895363zbMATH OpenFDO

Authors Yuefang Sun, Xueliang Li

Publication date 2 July 2012

Published in Utilitas Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

diametertriangle-freeedge-colored graphcomplement graphrainbow pathrainbow connection number

Mathematics Subject Classification ID

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

Abstract: A path in an edge-colored graph, where adjacent edges may be colored the same, is a rainbow path if no two edges of it are colored the same. A nontrivial connected graph $G$ is rainbow connected if there is a rainbow path connecting any two vertices, and the rainbow connection number of $G$, denoted by $rc(G)$, is the minimum number of colors that are needed in order to make $G$ rainbow connected. In this paper, we provide a new approach to investigate the rainbow connection number of a graph $G$ according to some constraints to its complement graph $$. We first derive that for a connected graph $G$, if $$ does not belong to the following two cases: $(i)$~$$, $$ contains exactly two connected components and one of them is trivial, then $rc(G)leq4$, where $diam(G)$ is the diameter of $G$. Examples are given to show that this bound is best possible. Next we derive that for a connected graph $G$, if $$ is triangle-free, then $rc(G)leq6$.

Recommendations

• Total rainbow connection number and complementary graph
• Rainbow connection number of comb product of graphs
• Total rainbow connection numbers of some special graphs
• scientific article; zbMATH DE number 6761154
• Rainbow connection numbers of middle and total graphs
• Rainbow connection numbers of Cayley graphs
• Proper rainbow connection number of graphs
• Rainbow connection number and independence number of a graph
• Rainbow numbers for matchings and complete graphs

Cited in

(11)

• Rainbow connection numbers of Cayley graphs
• scientific article; zbMATH DE number 6761154 (Why is no real title available?)
• Total rainbow connection number and complementary graph
• Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
• scientific article; zbMATH DE number 897189 (Why is no real title available?)
• Rainbow connection number and independence number of a graph
• Rainbow connection number of generalized composition
• Rainbow connection number of graph power and graph products
• Rainbow connection number and connected dominating sets
• On total rainbow \(k\)-connected graphs
• Proper connection numbers of complementary graphs

This page was built for publication: Rainbow connection numbers of complementary graphs

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