- Tytuł:
- Graphs with 3-Rainbow Index n − 1 and n − 2
- Autorzy:
-
Li, Xueliang
Schiermeyer, Ingo
Yang, Kang
Zhao, Yan - Powiązania:
- https://bibliotekanauki.pl/articles/31339126.pdf
- Data publikacji:
- 2015-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow S-tree
k-rainbow index - Opis:
- Let $G = (V(G),E(G))$ be a nontrivial connected graph of order $n$ with an edge-coloring $c : E(G) → {1, 2, . . ., q}, q ∈ \mathbb{N}$, 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 set $S ⊆ V (G)$, a tree connecting $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 $rx_k(G)$, where $k$ is an integer such that $2 ≤ k ≤ n$. Chartrand et al. got that the $k$-rainbow index of a tree is $n−1$ and the $k$-rainbow index of a unicyclic graph is $n−1$ or $n−2$. So there is an intriguing problem: Characterize graphs with the $k$-rainbow index $n − 1$ and $n − 2$. In this paper, we focus on $k = 3$, and characterize the graphs whose $3$-rainbow index is $n − 1$ and $n − 2$, respectively.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 105-120
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł