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

详细信息    查看全文

• 作者：Qingqiong Cai ^{cqqnjnu620@163.com" class="auth_mail" title="E-mail the corresponding author} ; Xueliang Li ; ^{lxl@nankai.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Yan Zhao ^{zhaoyan2010@mail.nankai.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Rainbow path ; Rainbow tree ; Dominating set ; kk-rainbow index
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 August 2016
• 年：2016
• 卷：209
• 期：Complete
• 页码：68-74
• 全文大小：384 K

文摘

A path in an edge-colored graph G$G$ is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph G$G$, denoted by rc(G)$rc\left(G\right)$, is the minimum number of colors that are needed to color the edges of G$G$ such that there is a rainbow path connecting every two vertices of G$G$. Similarly, a tree in G$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$G$ such that there is a rainbow tree containing all the vertices of S$S$ (other vertices may also be included in the tree) for each k$k$-subset S$S$ of V(G)$V\left(G\right)$ is called the k$k$-rainbow index of G$G$, denoted by rx_k(G)$r{x}_k\left(G\right)$, where k$k$ is an integer such that 2≤k≤n$2\le k\le n$. Chakraborty et al. got the following result: For every ϵ>0$ϵ>0$, a connected graph with minimum degree at least ϵn$ϵn$ has bounded rainbow connection number, where the bound depends only on ϵ$ϵ$. Krivelevich and Yuster proved that if G$G$ has n$n$ vertices and the minimum degree δ(G)$\delta \left(G\right)$ then rc(G)<20n/δ(G)$rc\left(G\right)<20n/\delta \left(G\right)$. This bound was later improved to 3n/(δ(G)+1)+3$3n/(\delta \left(G\right)+1)+3$ by Chandran et al. Since rc(G)=rx₂(G)$rc\left(G\right)=r{x}_2\left(G\right)$, a natural problem arises: for a general k$k$ determining the true behavior of rx_k(G)$r{x}_k\left(G\right)$ as a function of the minimum degree δ(G)$\delta \left(G\right)$. In this paper, we give upper bounds of rx_k(G)$r{x}_k\left(G\right)$ in terms of the minimum degree δ(G)$\delta \left(G\right)$ in different ways, namely, via Szemerédi’s Regularity Lemma, connected 2-step dominating sets, connected (k−1)$(k-1)$-dominating sets and k$k$-dominating sets of G$G$.