A note on the minimum size of k-rainbow-connected graphs

DOI10.1016/J.DISC.2014.04.024zbMATH Open1297.05086arXiv1506.03215OpenAlexW2003289864MaRDI QIDQ397136FDOQ397136

Allan Lo

Publication date: 8 August 2014

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: An edge-coloured graph $G$ is rainbow connected if there exists a rainbow path between any two vertices. A graph $G$ is said to be $k$-rainbow connected if there exists an edge-colouring of $G$ with at most $k$ colours that is rainbow connected. For integers $n$ and $k$, let $t(n,k)$ denote the minimum number of edges in $k$-rainbow connected graphs of order $n$. In this note, we prove that $t(n,k)=lceilk(n-2)/(k-1)ceil$ for all $n,kge3$

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

zbMATH Keywords

edge colouringrainbow connection

Mathematics Subject Classification ID

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

Cites Work

• Rainbow connections of graphs: a survey
• Rainbow connection in graphs
• On minimally rainbow \(k\)-connected graphs
• The minimum size of \(k\)-rainbow connected graphs of given order
• Smallest \(k\)-rainbow connected graphs for large \(k\)
• Note on minimally \(d\)-rainbow connected graphs

Cited In (6)

• Erdős-Gallai-type results for colorful monochromatic connectivity of a graph
• Some extremal results on the colorful monochromatic vertex-connectivity of a graph
• Rainbow connection number and graph operations
• Upper bounds of proper connection number of graphs
• More on the minimum size of graphs with given rainbow index
• The vertex-rainbow connection number of some graph operations

This page was built for publication: A note on the minimum size of \(k\)-rainbow-connected graphs

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