Menu
The \(k\)-rainbow index \(rx_k(G)\) of a connected graph \(G\) was introduced by Chartrand, Okamoto, and Zhang in 2010. Let \(G\) be a nontrivial connected graph with an edge-coloring \(c: E(G) \to \{1, 2, \ldots, q\}\), \(q \in \mathbb{N}\), 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 graph \(G = (V, E)\) and a set \(S \subseteq V\) of at least two vertices, an \(S\)-Steiner tree or a Steiner tree connecting \(S\) (or simply, an \(S\)-tree) is a subgraph \(T = (V’, E’)\) of \(G\) that is a tree with \(S \subseteq V’\). For \(S \subseteq V(G)\) and \(|S| \geq 2\), an \(S\)-Steiner tree \(T\) is said to be a rainbow \(S\)-tree if no two edges of \(T\) receive the same color. 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 \(k\)-rainbow index of \(G\), denoted by \(rx_k(G)\). In this paper, we consider when \(|S| = 3\). An upper bound of complete multipartite graphs is obtained. By this upper bound, for a connected graph \(G\) with \(\text{diam}(G) \geq 3\), we give an upper bound of its complementary graph.