Nemanja Draganić

collaborators

4 papers

cs.DS2023

Edge-disjoint paths in expanders: online with removals

Nemanja Draganić, Rajko Nenadov

We consider the problem of finding edge-disjoint paths between given pairs of vertices in a sufficiently strong $d$ -regular expander graph $G$ with $n$ vertices. In particular, we…

math.CO2023

Optimal Hamilton covers and linear arboricity for random graphs

Nemanja Draganić, Stefan Glock, David Munhá Correia +1

In his seminal 1976 paper, Pósa showed that for all $p \geq C lo g n / n$ , the binomial random graph $G (n, p)$ is with high probability Hamiltonian. This leads to the following natural…

math.CO2023

A generalization of Bondy's pancyclicity theorem

Nemanja Draganić, David Munhá Correia, Benny Sudakov

The bipartite independence number of a graph $G$ , denoted as $α ~ (G)$ , is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a + b = k + 1$ with the pro…

math.CO2023

Chvátal-Erdős condition for pancyclicity

Nemanja Draganić, David Munhá Correia, Benny Sudakov

An $n$ -vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$ . A celebrated…