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

DOI10.1016/J.DAM.2015.10.019MaRDI QIDQ298957zbMATH OpenOpenAlexFDO

Authors Qingqiong Cai, Xueliang Li, Yan Zhao

Publication date 21 June 2016

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

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

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)

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

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

Cites work

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

Cited in

(10)

• Rainbow connection number and connected dominating sets
• The \(k\)-proper index of graphs
• Rainbow connection numbers and the minimum degree sum of a graph
• Some upper bounds for the 3-proper index of graphs
• Note on the vertex-rainbow index of a graph
• The \((k,\ell )\)-proper index of graphs
• The vertex-rainbow index of a graph
• A survey on rainbow (vertex-)index of graphs
• scientific article; zbMATH DE number 6761154 (Why is no real title available?)
• Generalized rainbow connection 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)