The 3-Rainbow Index of a Graph

Lily Chen, et al. "The 3-Rainbow Index of a Graph." Discussiones Mathematicae Graph Theory 35.1 (2015): 81-94. <http://eudml.org/doc/271237>.

@article{LilyChen2015,
abstract = {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 subset S ⊆ V (G), a tree that connects 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-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper, we first determine the graphs of size m whose 3-rainbow index equals m, m − 1, m − 2 or 2. We also obtain the exact values of rx3(G) when G is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for rx3(G) when G is 2-connected and 2-edge connected. Graphs G for which rx3(G) attains this upper bound are determined.},
author = {Lily Chen, Xueliang Li, Kang Yang, Yan Zhao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow tree; S-tree; k-rainbow index; -tree; -rainbow index},
language = {eng},
number = {1},
pages = {81-94},
title = {The 3-Rainbow Index of a Graph},
url = {http://eudml.org/doc/271237},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Lily Chen
AU - Xueliang Li
AU - Kang Yang
AU - Yan Zhao
TI - The 3-Rainbow Index of a Graph
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 1
SP - 81
EP - 94
AB - 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 subset S ⊆ V (G), a tree that connects 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-subset S of V (G) is called the k-rainbow index of G, denoted by rxk(G). In this paper, we first determine the graphs of size m whose 3-rainbow index equals m, m − 1, m − 2 or 2. We also obtain the exact values of rx3(G) when G is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for rx3(G) when G is 2-connected and 2-edge connected. Graphs G for which rx3(G) attains this upper bound are determined.
LA - eng
KW - rainbow tree; S-tree; k-rainbow index; -tree; -rainbow index
UR - http://eudml.org/doc/271237
ER -