2013/10/10 by Qingqiong Cai, Xueliang Li, Cai, Qingqiong +3
Computer Science · Mathematics · #05C05 #05C15 #05C80 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C05 #msc:05C15 #msc:05C80 #msc:05D40
paper · pdf · doi:10.48550/arxiv.1310.2934
7 pages. arXiv admin note: substantial text overlap with arXiv:1212.6845, arXiv:1310.2783
arxiv created 2013/10/10 · openalex publication_date 2013/10/10 · arxiv updated 2013/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A tree in an edge colored graph is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers k, ℓ with k≥ 3, the (k,ℓ)-rainbow index rxk,ℓ(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 ℓ internally disjoint rainbow trees connecting S. This concept was introduced by Chartrand et. al., and there have been very few related results about it. In this paper, We establish a sharp threshold function for rxk,ℓ(Gn,p)≤ k and rxk,ℓ(Gn,M)≤ k, respectively, where Gn,p and Gn,M are the usually defined random graphs.