On the strong rainbow connection of a graph

zbMATH Open1268.05079arXiv1010.6139MaRDI QIDQ2376940FDOQ2376940

Authors: Yuefang Sun, Xueliang Li 

Publication date: 26 June 2013

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

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. For any two vertices $u$ and $v$ of $G$, a rainbow $u-v$ geodesic in $G$ is a rainbow $u-v$ path of length $d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. The graph $G$ is strongly rainbow connected if there exists a rainbow $u-v$ geodesic for any two vertices $u$ and $v$ in $G$. The strong rainbow connection number of $G$, denoted $src(G)$, is the minimum number of colors that are needed in order to make $G$ strong rainbow connected. In this paper, we first investigate the graphs with large strong rainbow connection numbers. Chartrand et al. obtained that $G$ is a tree if and only if $src(G)=m$, we will show that $src(G)eqm-1$, so $G$ is not a tree if and only if $src(G)leqm-2$, where $m$ is the number of edge of $G$. Furthermore, we characterize the graphs $G$ with $src(G)=m-2$. We next give a sharp upper bound for $src(G)$ according to the number of edge-disjoint triangles in graph $G$, and give a necessary and sufficient condition for the equality.

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

Recommendations

• The strong rainbow vertex-connection of graphs
• On proper (strong) rainbow connection of graphs
• On various (strong) rainbow connection numbers of graphs
• Rainbow and strong rainbow connection number for some families of graphs
• The rainbow connectivity of a graph
• On \(k\)-rainbow connection in graphs
• A sharp upper bound for the strong rainbow connection number of a graph
• Rainbow connections of graphs
• Rainbow connections of graphs
• scientific article; zbMATH DE number 7144826

zbMATH Keywords

edge-colored graphrainbow pathstrong rainbow connection numberedge-disjoint trianglerainbow geodesic

Mathematics Subject Classification ID

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

Cited In (15)

• Title not available (Why is that?)
• Rainbow and strong rainbow connection number for some families of graphs
• Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study
• The \((k,\ell)\)-rainbow index of random graphs
• Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
• (Strong) rainbow connection number of three classes of graphs
• Distance-local rainbow connection number
• On the rainbow vertex-connection
• On rainbow total-coloring of a graph
• On total rainbow \(k\)-connected graphs
• A sharp upper bound for the strong rainbow connection number of a graph
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• On various (strong) rainbow connection numbers of graphs
• Strong rainbow coloring of unicyclic graphs
• Proper connection number of graph products

This page was built for publication: On the strong rainbow connection of a graph

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