6 papers · 1 filter
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…
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…