The minimum size of graphs with given rainbow index

MaRDI QIDQ4645589zbMATH OpenFDO

Authors Thomas Y. H. Liu

Publication date 10 January 2019

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

zbMATH Keywords

edge coloringrainbow \(S\)-treerainbow connectionrainbow index

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: The concept of $k$-rainbow index $r{x}_k(G)$ of a connected graph $G$, introduced by Chartrand, Okamoto and Zhang, is a natural generalization of the rainbow connection number. Let $t(n,k,ell)$ denote the minimum size of a connected graph $G$ of order $n$ with $r{x}_k(G)leqell$, where $2leqellleqn-1$ and $2leqkleqn$. In this paper, we obtain some exact values and some upper bounds for $t(n,k,ell)$.

Recommendations

• Smallest k-rainbow connected graphs for large k
• Graphs with 3-rainbow index \(n-1\) and \(n-2\)
• The minimum size of \(k\)-rainbow connected graphs of given order
• A note on graphs with prescribed order and rainbow index
• The 3-rainbow index of a graph

Cited in

(17)

• On minimally rainbow k-connected graphs
• The 3-rainbow index of a graph
• More on the minimum size of graphs with given rainbow index
• Graphs with 4-rainbow index 3 and \(n-1\)
• The (k,)-rainbow index of random graphs
• The 3-rainbow index and connected dominating sets
• Solutions to conjectures on the (k,)-rainbow index of complete graphs
• Smallest k-rainbow connected graphs for large k
• Note on the upper bound of the rainbow index of a graph
• Rainbow trees in graphs and generalized connectivity
• Rainbow trees in small cubic graphs
• The \((k,\ell)\)-rainbow index for complete bipartite and multipartite graphs
• Some upper bounds for the 3-rainbow index of line graphs.
• A note on graphs with prescribed order and rainbow index
• The minimum size of \(k\)-rainbow connected graphs of given order
• A note on the minimum size of k-rainbow-connected graphs
• A survey on rainbow (vertex-)index of graphs

This page was built for publication: The minimum size of graphs with given rainbow index

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