Characterize graphs with rainbow connection numbers m-2 and m-3

zbMATH Open1305.05113arXiv1312.3068MaRDI QIDQ2938261FDOQ2938261

Authors: Yuefang Sun, Yan Zhao, Xueliang Li 

Publication date: 14 January 2015

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. Chartrand et al. obtained that $G$ is a tree if and only if $rc(G)=m$, and it is easy to see that $G$ is not a tree if and only if $rc(G)leqm-2$, where $m$ is the number of edge of $G$. So there is an interesting problem: Characterize the graphs $G$ with $rc(G)=m-2$. In this paper, we settle down this problem. Furthermore, we also characterize the graphs $G$ with $rc(G)=m-3$.

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

Recommendations

• Graphs with rainbow connection number two
• Rainbow connection in 3-connected graphs
• Rainbow connection in graphs
• Rainbow connection numbers of middle and total graphs
• Rainbow connection numbers of line graphs.

zbMATH Keywords

rainbow connection numberrainbow connected graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Connectivity (05C40)

Cited In (5)

• Characterizations of graphs having large proper connection numbers
• (Strong) rainbow connection on the splitting of 3-path
• Rainbow connection numbers of middle and total graphs
• The complexity of determining the vertex-rainbow index of graphs
• More on the colorful monochromatic connectivity

This page was built for publication: Characterize graphs with rainbow connection numbers \(m-2\) and \(m-3\)

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