2013/12/11 by Xueliang Li, Ingo Schiermeyer, Li, Xueliang +5
Mathematics · #05C05 #05C15 #05C75 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C05 #msc:05C15 #msc:05C75
paper · pdf · doi:10.48550/arxiv.1312.3069
11 pages
arxiv created 2013/12/23 · arxiv updated 2013/12/24
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 called a rainbow~tree if no two edges of T receive the same color. For a vertex set S⊆ V(G), a tree that connects S in G is called an \it 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 every k-set S of V(G) is called the \it k-rainbow index of G, denoted by rxk(G). Notice that an lower bound and an upper bound of the k-rainbow index of a graph with order n is k-1 and n-1, respectively. Chartrand et al. got that the k-rainbow index of a tree with order n is n-1 and the k-rainbow index of a unicyclic graph with order n is n-1 or n-2. Li and Sun raised the open problem of characterizing the graphs of order n with rxk(G)=n-1 for k≥ 3. In early papers we characterized the graphs of order n with 3-rainbow index 2 and n-1. In this paper, we focus on k=4, and characterize the graphs of order n with 4-rainbow index 3 and n-1, respectively.