2013/08/20 by Xueliang Li, Li, Xueliang, Kang Yang +3
Mathematics · #05C05 #05C15 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1308.4251
14 pages
arxiv created 2013/08/20 · arxiv updated 2013/08/21
Let G be a nontrivial connected graph with an edge-coloring c:E(G)→ \1,2,…,q\, q∈ ℕ, where adjacent edges may be colored the same. A tree T in G is a rainbow tree if no two edges of T receive the same color. For a vertex set S⊆ V(G), the tree connecting S in G is called an S-tree. The minimum number of colors that are needed in an edge-coloring of G such that there is a rainbow S-tree for each k-set S of V(G) is called the k-rainbow index of G, denoted by rxk(G). In \citeZhang, they got that the k-rainbow index of a tree is n-1 and the k-rainbow index of a unicyclic graph is n-1 or n-2. So there is an intriguing problem: Characterize graphs with the k-rainbow index n-1 and n-2. In this paper, we focus on k=3, and characterize the graphs whose 3-rainbow index is n-1 and n-2, respectively.