Přejít k obsahu


The rainbow connection number of 2-connected graphs

Citace: [] HOLUB, P. The rainbow connection number of 2-connected graphs. 2011.
Druh: PŘEDNÁŠKA, POSTER
Jazyk publikace: eng
Anglický název: The rainbow connection number of 2-connected graphs
Rok vydání: 2011
Autoři: RNDr. Přemysl Holub Ph.D.
Abstrakt CZ: Hranově obarvený graf G je duhově souvislý, jestliže každé dva vrcholy grafu G jsou spojeny cestou, jejíž hrany mají různé barvy. Číslo duhové souvislosti souvislého grafu G, značíme rc(G), je nejmenší počet barev potřebných k tomu, aby daný graf byl duhově souvislý. Caro a kol. ukázali, že pro 2-souvislé grafy na n vrcholech je rc(G) nejvýše n/2 + O(sqrt(n)). V této práci ukážeme, že pro 2-souvislé grafy platí rc(G) <= n/2+1.
Abstrakt EN: An edge-coloured graph $G$ is rainbow connected if any two vertices are connected by a path whose edges have different colours. The rainbow connection number of a connected graph $G$, denoted $rc(G)$, is the smallest number of colours that are needed in order to make $G$ rainbow connected. Caro et al. showed that, for a $2$-connected graph $G$ of order $n$, $rc(G)\leq \frac n2 + O(\sqrt{n})$. In this paper we prove that $rc(G)\leq \frac n2+1$ for any $2$-connected graph $G$.
Klíčová slova

Zpět

Patička