Szczegóły publikacji
Opis bibliograficzny
Rainbow connection in sparse graphs / Arnfried Kemnitz, Jakub PRZYBYŁO, Ingo Schiermeyer, Mariusz WOŹNIAK // Discussiones Mathematicae. Graph Theory ; ISSN 1234-3099. — 2013 — vol. 33 no. 1, s. 181–192. — Bibliogr. s. 191–192, Abstr.
Autorzy (4)
- Kemnitz Arnfried
- AGHPrzybyło Jakub
- Schiermeyer Ingo
- AGHWoźniak Mariusz
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 77270 |
|---|---|
| Data dodania do BaDAP | 2013-11-13 |
| Tekst źródłowy | URL |
| DOI | 10.7151/dmgt.1640 |
| Rok publikacji | 2013 |
| Typ publikacji | artykuł w czasopiśmie |
| Otwarty dostęp |  |
| Czasopismo/seria | Discussiones Mathematicae, Graph Theory |
Abstract
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 rc(G), is the minimum number of colours such that G is rainbow-connected. In this paper we prove that rc(G) <= k if vertical bar V(G)vertical bar= n and vertical bar E(G)vertical bar >= ((n-k+1) (2)) for all integers n and k with n - 6 <= k <= n - 3. We also show that this bound is tight.
