- Tytuł:
- Rainbow Connection In Sparse Graphs
- Autorzy:
-
Kemnitz, Arnfried
Przybyło, Jakub
Schiermeyer, Ingo
Woźniak, Mariusz - Powiązania:
- https://bibliotekanauki.pl/articles/30146690.pdf
- Data publikacji:
- 2013-03-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
rainbow-connected graph
rainbow colouring
rainbow connection number - Opis:
- An edge-coloured connected graph $G = (V,E)$ is called rainbow-connected if each pair of distinct vertices of $G$ is connected by a path whose edges have distinct colours. The rainbow connection number of $G$, denoted by $ \text{rc}(G)$, is the minimum number of colours such that $G$ is rainbow-connected. In this paper we prove that $ \text{rc}(G) \le k $ if $ |V (G)| = n $ and \( |E(G)| \ge \binom{n-k+1}{2} + k -1 \) for all integers $n$ and $k$ with $n − 6 \le k \le n − 3 $. We also show that this bound is tight.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2013, 33, 1; 181-192
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł