- Tytuł:
- Rainbow Connection Number of Dense Graphs
- Autorzy:
-
Li, Xueliang
Liu, Mengmeng
Schiermeyer, Ingo - Powiązania:
- https://bibliotekanauki.pl/articles/30146190.pdf
- Data publikacji:
- 2013-07-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge-colored graph
rainbow coloring
rainbow connection number - Opis:
- An edge-colored graph $G$ is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this paper we show that $rc(G) \leq 3$ if \( |E(G)| \geq \binom{n-2}{2} + 2 \), and $ rc(G) \leq 4 $ if \( |E(G)| \geq \binom{n-3}{2} + 3 \). These bounds are sharp.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 3; 603-611
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł