The vertex-rainbow index of a graph

Original · EN

The k-rainbow index rxₖ(G) of a connected graph G was introduced by Chartrand, Okamoto and Zhang in 2010. As a natural counterpart of the k-rainbow index, we introduced the concept of k-vertex-rainbow index rvxₖ(G) in this paper. For a graph G=(V,E) and a set S V of at least two vertices, an S-Steiner tree or a Steiner tree connecting S (or simply, an S-tree) is a such subgraph T=(V',E') of G that is a tree with S V'. For S V(G) and |S|≥ 2, an S-Steiner tree T is said to be a vertex-rainbow S-tree if the vertices of V(T) S have distinct colors. For a fixed integer k with 2≤ k≤ n, the vertex-coloring c of G is called a k-vertex-rainbow coloring if for every k-subset S of V(G) there exists a vertex-rainbow S-tree. In this case, G is called vertex-rainbow k-tree-connected. The minimum number of colors that are needed in a k-vertex-rainbow coloring of G is called the k-vertex-rainbow index of G, denoted by rvxₖ(G). When k=2, rvx₂(G) is nothing new but the vertex-rainbow connection number rvc(G) of G. In this paper, sharp upper and lower bounds of srvxₖ(G) are given for a connected graph G of order n,that is, 0≤ srvxₖ(G)≤ n-2. We obtain the Nordhaus-Guddum results for 3-vertex-rainbow index, and show that rvx₃(G)+rvx₃(G)=4 for n=4 and 2≤ rvx₃(G)+rvx₃(G)≤ n-1 for n≥ 5. Let t(n,k,ℓ) denote the minimal size of a connected graph G of order n with rvxₖ(G)≤ ℓ, where 2≤ ℓ≤ n-2 and 2≤ k≤ n. The upper and lower bounds for t(n,k,ℓ) are also obtained.