1 citations · 1 across the 7 of their papers we have counts for
12 papers
New tools for sparse graph embeddings: Hybrid expanders and application to nested cycles
Nemanja Draganić
We introduce \emph{hybrid expanders}, sparse graphs which combine sublinear expansion across all scales with strong constant-factor expansion on smaller, polylogarithmic sets. We s…
Efficient Hamilton covers and linear arboricity of random graphs
Nemanja Draganić, Michael Krivelevich
A Hamilton cover of a graph is a collection of Hamilton cycles whose union contains all edges. Since each Hamilton cycle covers two edges at every vertex, every Hamilton cover has…
Cycle-factors of regular graphs via entropy
Micha Christoph, Nemanja Draganić, António Girão +3
It is a classical result that a random permutation of elements has, on average, about cycles. We generalise this fact to all directed -regular graphs on vertice…
Disjoint connected dominating sets in pseudorandom graphs
Nemanja Draganić, Michael Krivelevich
A connected dominating set (CDS) in a graph is a dominating set of vertices that induces a connected subgraph. Having many disjoint CDSs in a graph can be considered as a measure o…
Cycles with many chords
Nemanja Draganić, Abhishek Methuku, David Munhá Correia +1
How many edges in an -vertex graph will force the existence of a cycle with as many chords as it has vertices? Almost 30 years ago, Chen, Erdős and Staton considered this questi…
Effective bounds for induced size-Ramsey numbers of cycles
Domagoj Bradač, Nemanja Draganić, Benny Sudakov
The induced size-Ramsey number of a graph is the smallest number of edges a (host) graph can have such that for any -coloring of its edges, the…
Size-Ramsey numbers of graphs with maximum degree three
Nemanja Draganić, Kalina Petrova
The size-Ramsey number of a graph is the smallest number of edges a (host) graph can have, such that for any red/blue colouring of , there is a monochromati…
The largest hole in sparse random graphs
Nemanja Draganić, Stefan Glock, Michael Krivelevich
We show that for any with , with high probability, the size of a largest induced cycle in the random graph is . T…
Tight bound for powers of Hamilton cycles in tournaments
Nemanja Draganić, David Munhá Correia, Benny Sudakov
A basic result in graph theory says that any -vertex tournament with in- and out-degrees larger than contains a Hamilton cycle, and this is tight. In 1990, Bollo…
Rolling backwards can move you forward: on embedding problems in sparse expanders
Nemanja Draganić, Michael Krivelevich, Rajko Nenadov
We develop a general embedding method based on the Friedman-Pippenger tree embedding technique (1987) and its algorithmic version, essentially due to Aggarwal et al. (1996), enhanc…
The size-Ramsey number of short subdivisions
Nemanja Draganić, Michael Krivelevich, Rajko Nenadov
The -size-Ramsey number of a graph is the smallest number of edges a graph can have, such that for every edge-coloring of with colors there exists…
A Ramsey Theorem for Multiposets
Nemanja Draganić, Dragan Mašulović
In the parlance of relational structures, the Finite Ramsey Theorem states that the class of all finite chains has the Ramsey property. A classical result of J. Nešetřil and V. Röd…