Graphs with 4-Rainbow Index 3 and n − 1

@article{XueliangLi2015,
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 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 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 set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a 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.},
author = {Xueliang Li, Ingo Schiermeyer, Kang Yang, Yan Zhao},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {rainbow S-tree; k-rainbow index; rainbow -tree; -rainbow index},
language = {eng},
number = {2},
pages = {387-398},
title = {Graphs with 4-Rainbow Index 3 and n − 1},
url = {http://eudml.org/doc/271092},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Xueliang Li
AU - Ingo Schiermeyer
AU - Kang Yang
AU - Yan Zhao
TI - Graphs with 4-Rainbow Index 3 and n − 1
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 387
EP - 398
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 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 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 set S of k vertices of V (G) is called the k-rainbow index of G, denoted by rxk(G). Notice that a 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.
LA - eng
KW - rainbow S-tree; k-rainbow index; rainbow -tree; -rainbow index
UR - http://eudml.org/doc/271092
ER -