The \((k,\ell )\) -Rainbow Index for Complete Bipartite and Multipartite Graphs

详细信息    查看全文

• 作者：Qingqiong Cai ; Xueliang Li ; Jiangli Song
• 刊名：Bulletin of the Malaysian Mathematical Sciences Society
• 出版年：2016
• 出版时间：July 2016
• 年：2016
• 卷：39
• 期：3
• 页码：1225-1236
• 全文大小：460 KB
• 刊物类别：Mathematics, general; Applications of Mathematics;
• 刊物主题：Mathematics, general; Applications of Mathematics;
• 出版者：Springer Singapore
• ISSN：2180-4206
• 卷排序：39

文摘

A tree in an edge-colored graph G is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers k, \(\ell \) with \(k\ge 3\), the \((k,\ell )\)-rainbow index\(rx_{k,\ell }(G)\) of G is the minimum number of colors needed in an edge-coloring of G such that for any set S of k vertices of G, there exist \(\ell \) internally disjoint rainbow trees connecting S. This concept was introduced by Chartrand et al. in 2010. It is very difficult to determine the \((k,\ell )\)-rainbow index for a general graph. Chartrand et al. determined the (k, 1)-rainbow index of all unicyclic graphs and the \((3,\ell )\)-rainbow index of complete graphs for \(\ell =1,2\). We showed that for every pair of positive integers \(k,\ell \) with \(k\ge 3\), there exists a positive integer \(N=N(k,\ell )\) such that \(rx_{k,\ell }(K_{n})=k\) for every integer \(n\ge N\), which settled down a conjecture of Chartrand et al. In this paper, we use probabilistic method and bipartite Ramsey numbers to obtain similar results of the \((k,\ell )\)-rainbow index for complete bipartite graphs. For complete multipartite graphs, we get similar results for most cases, however, since there is no any result on the multipartite Ramsey numbers in general, we can only get a value that differs by 1 from the exact value for some cases.KeywordsRainbow indexComplete bipartite (Multipartite) graphs Probabilistic method(Bipartite) Ramsey number