R. Nenadov

activity

20162026

most citedAn O(n) time algorithm for finding Hamilton cycles with high probability

2 citations · 5 across the 23 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

math.CO2017

Monochromatic cycle covers in random graphs

Dániel Korándi, Frank Mousset, Rajko Nenadov +2

A classic result of Erdős, Gyárfás and Pyber states that for every coloring of the edges of $K_{n}$ with $r$ colors, there is a cover of its vertex set by at most $f(r) = O(r^2 \log…

math.CO2017

Resilience of Perfect Matchings and Hamiltonicity in Random Graph Processes

Rajko Nenadov, Angelika Steger, Miloš Trujić

Let ${G_{i}}$ be the random graph process: starting with an empty graph $G_{0}$ with $n$ vertices, in every step $i \geq 1$ the graph $G_{i}$ is formed by taking an edge chosen uniform…

math.CO2017

Spanning universality in random graphs

Asaf Ferber, Rajko Nenadov

A graph is said to be $H (n, Δ)$ -universal if it contains every graph on $n$ vertices with maximum degree at most $Δ$ . Using a `matching-based' embedding technique introdu…