On the strong rainbow connection of a graph

MaRDI QIDQ2376940zbMATH OpenFDO

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)

Full work available at URL https://arxiv.org/abs/1010.6139, http://math.usm.my/bulletin/html/vol36_2_5.html

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)

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.

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
• scientific article; zbMATH DE number 7144826

Cited in

(17)

• On total rainbow \(k\)-connected graphs
• On rainbow total-coloring of a graph
• (Strong) rainbow connection number of three classes of graphs
• Distance-local rainbow connection number
• An integer program and new lower bounds for computing the strong rainbow connection numbers of graphs
• Strong rainbow coloring of unicyclic graphs
• Rainbow subgraphs in edge-colored planar and outerplanar graphs
• On the rainbow vertex-connection
• scientific article; zbMATH DE number 7144826 (Why is no real title available?)
• Rainbow and strong rainbow connection number for some families of graphs
• Proper connection number of graph products
• Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total-connection number
• Rainbow \(C_4\)'s and directed \(C_4\)'s: the bipartite case study
• The \((k,\ell)\)-rainbow index of random graphs
• Multicolour paths in graphs: NP-hardness, algorithms, and applications on routing in WDM networks
• On various (strong) rainbow connection numbers of graphs
• A sharp upper bound for the strong rainbow connection number of a graph

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)