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