# Bojan Mohar: Mavrična povezanost družin slučajnih grafov (Rainbow connectivity of families of random graphs)

Predavatelj:

**Bojan Mohar **
(SFU in IMFM)

Naslov:

**Mavrična povezanost družin slučajnih grafov
(Rainbow connectivity of families of random graphs)**

Povzetek:

Given a family *G* that contains *s* graphs on a common vertex set *X*, we say
that *G* is rainbow connected if for every vertex pair *u,v* in *X*, there
exists a path from *u* to *v* that uses at most one edge from each graph in
*G*. We consider the case that *G* contains *s* graphs, each sampled randomly
from *G*(*n,p*), with *n* = |*X*| and *p = c* log *n* / *sn*, where *c* > 1 is a
constant. We show that when *s* is sufficiently large, *G* is a.a.s. rainbow
connected, and when s is sufficiently small, *G* is a.a.s. not rainbow
connected. We also calculate a threshold of *s* for the rainbow
connectivity of *G*, and we show that this threshold is concentrated on at
most three values.

This is joint work with Peter Bradshaw.