- Tytuł:
- The 3-Rainbow Index of a Graph
- Autorzy:
-
Chen, Lily
Li, Xueliang
Yang, Kang
Zhao, Yan - Powiązania:
- https://bibliotekanauki.pl/articles/31339122.pdf
- Data publikacji:
- 2015-02-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow tree
S-tree
k-rainbow index - Opis:
- 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 $rx_k(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 $rx_3(G)$ when $G$ is a regular multipartite complete graph or a wheel. Finally, we give a sharp upper bound for $rx_3(G)$ when $G$ is 2-connected and 2-edge connected. Graphs $G$ for which $rx_3(G)$ attains this upper bound are determined.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2015, 35, 1; 81-94
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł