David Munhá Correia

most citedHamiltonicity of expanders: optimal bounds and applications

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

collaborators

5 papers

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.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

Hamilton cycles in pseudorandom graphs

Stefan Glock, David Munhá Correia, Benny Sudakov

Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$ -regular $n$ …

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…