On various (strong) rainbow connection numbers of graphs

MaRDI QIDQ5374232zbMATH OpenFDO

Authors

Publication date 10 April 2018

Full work available at URL https://arxiv.org/abs/1601.01063, http://ajc.maths.uq.edu.au/pdf/70/ajc_v70_p137.pdf

zbMATH Keywords

rainbow geodesic

Mathematics Subject Classification ID

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

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$.

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

Cites work

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

Cited in

(6)

• scientific article; zbMATH DE number 7144826 (Why is no real title available?)
• On the strong rainbow connection of a graph
• Distance-local rainbow connection number
• scientific article; zbMATH DE number 6837036 (Why is no real title available?)
• On total rainbow \(k\)-connected graphs
• Total rainbow connection of digraphs

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)