Note on the upper bound of the rainbow index of a graph

DOI10.1016/J.DAM.2015.10.019zbMATH Open1339.05118arXiv1407.4663OpenAlexW2098102372MaRDI QIDQ298957FDOQ298957

Authors: Qingqiong Cai, Xueliang Li, Yan Zhao 

Publication date: 21 June 2016

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

Abstract: A path in an edge-colored graph $G$, where adjacent edges may be colored the same, is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph $G$, denoted by $rc(G)$, is the minimum number of colors that are needed to color the edges of $G$ such that there exists a rainbow path connecting every two vertices of $G$. Similarly, a tree in $G$ is a rainbow~tree if no two edges of it receive the same color. The minimum number of colors that are needed in an edge-coloring of $G$ such that there is a rainbow tree connecting $S$ for each $k$-subset $S$ of $V(G)$ is called the $k$-rainbow index of $G$, denoted by $r{x}_k(G)$, where $k$ is an integer such that $2leqkleqn$. Chakraborty et al. got the following result: For every $epsilon>0$, a connected graph with minimum degree at least $epsilonn$ has bounded rainbow connection, where the bound depends only on $epsilon$. Krivelevich and Yuster proved that if $G$ has $n$ vertices and the minimum degree $delta(G)$ then $rc(G)<20n/delta(G)$. This bound was later improved to $3n/(delta(G)+1)+3$ by Chandran et al. Since $rc(G)=r{x}_2(G)$, a natural problem arises: for a general $k$ determining the true behavior of $r{x}_k(G)$ as a function of the minimum degree $delta(G)$. In this paper, we give upper bounds of $r{x}_k(G)$ in terms of the minimum degree $delta(G)$ in different ways, namely, via Szemer'{e}di's Regularity Lemma, connected $2$-step dominating sets, connected $(k-1)$-dominating sets and $k$-dominating sets of $G$.

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

Recommendations

• The rainbow connection of a graph is (at most) reciprocal to its minimum degree
• Rainbow connection number and connected dominating sets
• On rainbow connection
• Rainbow connection and minimum degree
• The minimum size of graphs with given rainbow index

zbMATH Keywords

dominating set\(k\)-rainbow indexrainbow pathrainbow tree

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Cites Work

• Graph theory
• On rainbow connection
• Rainbow connections of graphs
• The 3-rainbow index of a graph
• The 3-rainbow index and connected dominating sets
• Solutions to conjectures on the \((k,\ell)\)-rainbow index of complete graphs
• Some upper bounds for 3-rainbow index of graphs
• Rainbow connection number and connected dominating sets
• Rainbow trees in graphs and generalized connectivity
• Rainbow connection in graphs
• Connected Domination and Spanning Trees with Many Leaves
• Hardness and algorithms for rainbow connection
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited In (10)

• Generalized rainbow connection of graphs
• Title not available (Why is that?)
• The \((k,\ell )\)-proper index of graphs
• The vertex-rainbow index of a graph
• The \(k\)-proper index of graphs
• Rainbow connection numbers and the minimum degree sum of a graph
• Note on the vertex-rainbow index of a graph
• Some upper bounds for the 3-proper index of graphs
• Rainbow connection number and connected dominating sets
• A survey on rainbow (vertex-)index of graphs

This page was built for publication: Note on the upper bound of the rainbow index of a graph

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