N. Dragani'c

activity

20192026

most citedUniversal and unavoidable graphs

5 citations · 9 across the 19 of their papers we have counts for

collaborators

24 papers

math.CO2026

The Lovász conjecture holds for moderately dense Cayley graphs

Benjamin Bedert, Nemanja Draganić, Alp Müyesser +1

We show that there is an absolute constant $c > 0$ such that every large connected $n$ -vertex Cayley graph with degree $d \geq n^{1 - c}$ has a Hamilton cycle. This makes progress towar…

math.CO2026

Cycles with almost linearly many chords

Nemanja Draganić, António Girão

We prove that constant minimum degree already forces cycles with almost linearly many chords. Specifically, every graph $G$ with $δ (G) \geq C$ contains a cycle of length $ℓ \geq 4$ …

math.CO2025

On Independent Spanning Trees in Random and Pseudorandom Graphs

Nemanja Draganić, Keith Frankston, Michael Krivelevich +2

In 1989, Zehavi and Itai conjectured that every $k$ -connected graph contains $k$ independent spanning trees rooted at any prescribed vertex $r$ . That is, for each vertex $v$ , the u…

math.CO2025

Hamilton cycles in pseudorandom graphs: resilience and approximate decompositions

Nemanja Draganić, Jaehoon Kim, Hyunwoo Lee +3

Dirac's classical theorem asserts that, for $n \geq 3$ , any $n$ -vertex graph with minimum degree at least $n /2$ is Hamiltonian. Furthermore, if we additionally assume that such grap…

math.CO2025

New bounds for linear arboricity and related problems

Micha Christoph, Nemanja Draganić, António Girão +3

A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture states that every graph of maximum degree $Δ$ can be decomposed into at most $\lceil(Δ+1)…

math.CO2025

Cyclic subsets in regular Dirac graphs

Nemanja Draganić, Peter Keevash, Alp Müyesser

In 1996, in his last paper, Erdős asked the following question that he formulated together with Faudree: is there a positive $c$ such that any $(n + 1)$ -regular graph $G$ on $2 n$ ver…

math.CO2025

Pósa rotation through a random permutation

Nemanja Draganić, Peter Keevash

What minimum degree of a graph $G$ on $n$ vertices guarantees that the union of $G$ and a random $2$ -factor (or permutation) is with high probability Hamiltonian? Girão and Espuny…

math.CO2024★ 1 cited

Hamiltonicity of expanders: optimal bounds and applications

Nemanja Draganić, Richard Montgomery, David Munhá Correia +2

An $n$ -vertex graph $G$ is a $C$ -expander if $∣ N (X) ∣ \geq C ∣ X ∣$ for every $X \subseteq V (G)$ with $∣ X ∣ < n /2 C$ and there is an edge between every two disjoint sets of at least $n /2 C$ …

math.CO2024

Long induced paths in expanders

Nemanja Draganić, Peter Keevash

We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, s…

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

Size-Ramsey numbers of structurally sparse graphs

Nemanja Draganić, Marc Kaufmann, David Munhá Correia +2

Size-Ramsey numbers are a central notion in combinatorics and have been widely studied since their introduction by Erdős, Faudree, Rousseau and Schelp in 1978. Research has mainly…

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…

math.CO2022

Pancyclicity of Hamiltonian graphs

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$ . In 1972, Erd…

math.CO2021

Tight bounds for divisible subdivisions

Shagnik Das, Nemanja Draganić, Raphael Steiner

Alon and Krivelevich proved that for every $n$ -vertex subcubic graph $H$ and every integer $q \geq 2$ there exists a (smallest) integer $f = f (H, q)$ such that every $K_{f}$ -minor contai…

math.CO2021

Ramsey number of 1-subdivisions of transitive tournaments

Nemanja Draganić, David Munhá Correia, Benny Sudakov +1

The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided…

math.CO2021

Short proofs for long induced paths

Nemanja Draganić, Stefan Glock, Michael Krivelevich

We present a modification of the Depth first search algorithm, suited for finding long induced paths. We use it to give simple proofs of the following results. We show that the ind…

math.CO2020

Unavoidable hypergraphs

M. Bucić, N. Draganić, B. Sudakov +1

The following very natural problem was raised by Chung and Erdős in the early 80's and has since been repeated a number of times. What is the minimum of the Turán number $\text{ex}…

math.CO2020

A Note on Powers of Paths in Tournaments

Nemanja Draganić, David Munhá Correia, Benny Sudakov

In this note we show that every tournament on $n$ vertices contains the $k$ -th power of a directed path of length $n / 2^{6 k + 7}$ , which improves upon the recent bound of Scott and Ko…

math.CO2020

Powers of paths in tournaments

Nemanja Draganić, François Dross, Jacob Fox +7

In this short note we prove that every tournament contains the $k$ -th power of a directed path of linear length. This improves upon recent results of Yuster and of Girão. We also g…

math.CO2020★ 3 cited

Large induced trees in dense random graphs

Nemanja Draganić

Erdős and Palka initiated the study of the maximal size of induced trees in random graphs in 1983. They proved that for every fixed $0 < p < 1$ the size of a largest induced tree in $G…

math.CO2020

Large induced matchings in random graphs

Oliver Cooley, Nemanja Draganić, Mihyun Kang +1

Given a large graph $H$ , does the binomial random graph $G (n, p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extens…

math.CO2019★ 5 cited

Universal and unavoidable graphs

Matija Bucić, Nemanja Draganić, Benny Sudakov

The Turán number $ex (n, H)$ of a graph $H$ is the maximal number of edges in an $H$ -free graph on $n$ vertices. In $1983$ Chung and Erdős asked which graphs $H$ with $e$ edge…