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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ is a rainbow path if every two edges of it receive distinct colors. The rainbow connection number of a connected graph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, denoted by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si3.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3e5d94194cad0bbc51e8ce7cff98f102" title="Click to view the MathML source">rc(G)class="mathContainer hidden">class="mathCode">$rc\left(G\right)$, is the minimum number of colors that are needed to color the edges of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ such that there is a rainbow path connecting every two vertices of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$. Similarly, a tree in class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ such that there is a rainbow tree containing all the vertices of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=a010d8a5a38bd02ef378a520e6dc9837" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$ (other vertices may also be included in the tree) for each class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3a6c10c018d74eac08c03ecea5ba8346" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-subset class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si8.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=a010d8a5a38bd02ef378a520e6dc9837" title="Click to view the MathML source">Sclass="mathContainer hidden">class="mathCode">$S$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si11.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=14eec98fff69b69c62ef21a344f5ebb5" title="Click to view the MathML source">V(G)class="mathContainer hidden">class="mathCode">$V\left(G\right)$ is called the class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3a6c10c018d74eac08c03ecea5ba8346" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-rainbow index of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$, denoted by class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si14.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=fcc70de2ea9c8d433527bcf24e32ae91" title="Click to view the MathML source">rx_k(G)class="mathContainer hidden">class="mathCode">$r{x}_k\left(G\right)$, where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3a6c10c018d74eac08c03ecea5ba8346" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ is an integer such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si16.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=371e4a4659754921450754cead0d115d" title="Click to view the MathML source">2≤k≤nclass="mathContainer hidden">class="mathCode">$2\le k\le n$. Chakraborty et al. got the following result: For every class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si17.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=ed8c7fee753cd784503af95367d39551" title="Click to view the MathML source">ϵ>0class="mathContainer hidden">class="mathCode">$ϵ>0$, a connected graph with minimum degree at least class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si18.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=be1242350eae1e7755702f730c8c60e0" title="Click to view the MathML source">ϵnclass="mathContainer hidden">class="mathCode">$ϵn$ has bounded rainbow connection number, where the bound depends only on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si19.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=4535099ed572d58ca1594236e9e7fd26" title="Click to view the MathML source">ϵclass="mathContainer hidden">class="mathCode">$ϵ$. Krivelevich and Yuster proved that if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$ has class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si21.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=c3b2016a3f1f8f4b1dec805314098be4" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ vertices and the minimum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=7d6892f8f15af19a6f478506563c1750" title="Click to view the MathML source">δ(G)class="mathContainer hidden">class="mathCode">$\delta \left(G\right)$ then class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si23.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=2fcab91efa8de83c9157c7ca8b73885c" title="Click to view the MathML source">rc(G)<20n/δ(G)class="mathContainer hidden">class="mathCode">$rc\left(G\right)<20n/\delta \left(G\right)$. This bound was later improved to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si24.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=65b0dea0b7e2e3d348b9f0f2e5b7d18b" title="Click to view the MathML source">3n/(δ(G)+1)+3class="mathContainer hidden">class="mathCode">$3n/(\delta \left(G\right)+1)+3$ by Chandran et al. Since class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si25.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=60555fb6f76ea6c51e13b94eda549928" title="Click to view the MathML source">rc(G)=rx₂(G)class="mathContainer hidden">class="mathCode">$rc\left(G\right)=r{x}_2\left(G\right)$, a natural problem arises: for a general class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3a6c10c018d74eac08c03ecea5ba8346" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$ determining the true behavior of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si14.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=fcc70de2ea9c8d433527bcf24e32ae91" title="Click to view the MathML source">rx_k(G)class="mathContainer hidden">class="mathCode">$r{x}_k\left(G\right)$ as a function of the minimum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=7d6892f8f15af19a6f478506563c1750" title="Click to view the MathML source">δ(G)class="mathContainer hidden">class="mathCode">$\delta \left(G\right)$. In this paper, we give upper bounds of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si14.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=fcc70de2ea9c8d433527bcf24e32ae91" title="Click to view the MathML source">rx_k(G)class="mathContainer hidden">class="mathCode">$r{x}_k\left(G\right)$ in terms of the minimum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=7d6892f8f15af19a6f478506563c1750" title="Click to view the MathML source">δ(G)class="mathContainer hidden">class="mathCode">$\delta \left(G\right)$ in different ways, namely, via Szemerédi’s Regularity Lemma, connected 2-step dominating sets, connected class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si31.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=80e87a2498f1f74d37e0e268b2c9cd08" title="Click to view the MathML source">(k−1)class="mathContainer hidden">class="mathCode">$(k-1)$-dominating sets and class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si9.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=3a6c10c018d74eac08c03ecea5ba8346" title="Click to view the MathML source">kclass="mathContainer hidden">class="mathCode">$k$-dominating sets of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005065&_mathId=si1.gif&_user=111111111&_pii=S0166218X15005065&_rdoc=1&_issn=0166218X&md5=403d9f596f8e43b2f543fcd9ecf1a3c7" title="Click to view the MathML source">Gclass="mathContainer hidden">class="mathCode">$G$.