On various (strong) rainbow connection numbers of graphs

zbMATH Open1383.05177arXiv1601.01063MaRDI QIDQ5374232FDOQ5374232

Author name not available (Why is that?)

Publication date: 10 April 2018

Abstract: An edge-coloured path is emph{rainbow} if all the edges have distinct colours. For a connected graph $G$, the emph{rainbow connection number} $rc(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow path. Similarly, the emph{strong rainbow connection number} $src(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two concepts of connectivity in graphs were introduced by Chartrand et al.~in 2008. Subsequently, vertex-coloured versions of both parameters, $rvc(G)$ and $srvc(G)$, and a total-coloured version of the rainbow connection number, $trc(G)$, were introduced. In this paper we introduce the strong total rainbow connection number $strc(G)$, which is the version of the strong rainbow connection number using total-colourings. Among our results, we will determine the strong total rainbow connection numbers of some special graphs. We will also compare the six parameters, by considering how close and how far apart they can be from one another. In particular, we will characterise all pairs of positive integers $a$ and $b$ such that, there exists a graph $G$ with $trc(G)=a$ and $strc(G)=b$, and similarly for the functions $rvc$ and $srvc$.

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

Recommendations

• Total rainbow connection of digraphs
• (Strong) rainbow connection number of three classes of graphs
• Rainbow connection in graphs
• On the strong rainbow connection of a graph
• Total rainbow \(k\)-connection in graphs

zbMATH Keywords

rainbow geodesic

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• On rainbow connection
• Rainbow connections of graphs: a survey
• Note on the hardness of rainbow connections for planar and line graphs
• On the strong rainbow connection of a graph
• Rainbow connection in graphs
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• The complexity of determining the rainbow vertex-connection of a graph
• On the rainbow vertex-connection
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Total rainbow \(k\)-connection in graphs
• The strong rainbow vertex-connection of graphs
• Hardness and Algorithms for Rainbow Connectivity
• Further hardness results on the rainbow vertex-connection number of graphs
• Total rainbow connection number and complementary graph
• On total rainbow \(k\)-connected graphs
• Upper bounds for the total rainbow connection of graphs
• Tight upper bound of the rainbow vertex-connection number for 2-connected graphs
• Rainbow vertex \(k\)-connection in graphs
• Note on rainbow connection in oriented graphs with diameter 2
• Rainbow connection in oriented graphs
• On rainbow total-coloring of a graph
• Rainbow connection in some digraphs
• Rainbow vertex connection of digraphs
• Rainbow connectivity of cacti and of some infinite digraphs
• Total rainbow connection of digraphs
• The (strong) rainbow connection numbers of Cayley graphs on abelian groups
• A solution to a conjecture on the rainbow connection number

Cited In (5)

• Title not available (Why is that?)
• On the strong rainbow connection of a graph
• Distance-local rainbow connection number
• Title not available (Why is that?)
• On total rainbow \(k\)-connected graphs

This page was built for publication: On various (strong) rainbow connection numbers of graphs

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