- Tytuł:
- Graphs with 4-Rainbow Index 3 and n − 1
- Autorzy:
-
Li, Xueliang
Schiermeyer, Ingo
Yang, Kang
Zhao, Yan - Powiązania:
- https://bibliotekanauki.pl/articles/31339468.pdf
- Data publikacji:
- 2015-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow S-tree
k-rainbow index - Opis:
- Let $G$ be a nontrivial connected graph with an edge-coloring $ c : E(G) \rightarrow $ $ {1, 2, . . ., 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 vertex set $ S \subseteq 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 $ r x_k (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 $r x_k (G) = n − 1$ for $ k \ge 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 2; 387-398
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł