A solution to a conjecture on two rainbow connection numbers of a graph.

zbMATH Open1274.05151arXiv1012.2693MaRDI QIDQ4909692FDOQ4909692

Authors: Xiaolin Chern, Xueliang Li 

Publication date: 21 March 2013

Abstract: For a graph $G$, Chartrand et al. defined the rainbow connection number $rc(G)$ and the strong rainbow connection number $src(G)$ in "G. Charand, G.L. John, K.A. Mckeon, P. Zhang, Rainbow connection in graphs, Mathematica Bohemica, 133(1)(2008) 85-98". They raised the following conjecture: for two given positive $a$ and $b$, there exists a connected graph $G$ such that $rc(G)=a$ and $src(G)=b$ if and only if $a=bin1,2$ or $3leqaleqb$". In this short note, we will show that the conjecture is true.

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

Recommendations

• Rainbow connection number and connectivity
• Graphs with rainbow connection number two
• Rainbow connection in graphs
• (Strong) rainbow connection number of three classes of graphs
• The rainbow connection number of 2-connected graphs

zbMATH Keywords

edge-colored graph(strong) rainbow connection number(strong) rainbow coloring

Mathematics Subject Classification ID

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

Cited In (4)

• Rainbow connections of graphs
• The \(k\)-proper index of graphs
• Distance-local rainbow connection number
• On various (strong) rainbow connection numbers of graphs

This page was built for publication: A solution to a conjecture on two rainbow connection numbers of a graph.

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