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

MaRDI QIDQ2938261zbMATH OpenFDO

Authors Yuefang Sun, Yan Zhao, Xueliang Li

Publication date 14 January 2015

Full work available at URL https://arxiv.org/abs/1312.3068, http://ajc.maths.uq.edu.au//pdf/60/ajc_v60_p306.pdf

zbMATH Keywords

rainbow connection numberrainbow connected graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) 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. 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$.

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.

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)