Mathematical Computer Science Seminar
Andrzej Dudek
Western Michigan University
Powers of Hamiltonian cycles in randomly augmented graphs
Abstract: It follows from the theorems of Dirac and of Koml\'os, Sark\"ozy, and Szemer\'edi, who
confirmed the Pos\'a-Seymour conjecture, that for every $k\ge 1$
and sufficiently large $n$ already the minimum degree $\delta(G) \ge \frac{k}{k+1} n$
for an $n$-vertex graph $G$ alone suffices to ensure the existence of the $k$-th power of a Hamiltonian cycle.
In this talk we will determine the number of random edges one has to add to a graph $G$ with minimum degree $\delta(G) \ge \left(\frac{k}{k+1} +\varepsilon\right)n$ (with $\varepsilon>0$) in order to create an $\ell$-th power of a Hamiltonian cycle, where $\ell\ge k+1$.
This is joint work with Sylwia Antoniuk, Christian Reiher, Andrzej Ruci\'nski and Mathias Schacht.
Monday April 29, 2019 at 3:00 PM in 427 SEO