The Kőnig Graph Process

Nina Kamčev; Michael Krivelevich; Natasha Morrison; Benny Sudakov

paper

The Kőnig Graph Process

arXiv:1906.04806

Abstract

Say that a graph G has property $K$ if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set $N := (2 n)$ and let $e_{1}, e_{2}, \dots e_{N}$ be a uniformly random ordering of the edges of $K_{n}$ , with $n$ an even integer. Let $G_{0}$ be the empty graph on $n$ vertices. For $m \geq 0$ , $G_{m + 1}$ is obtained from $G_{m}$ by adding the edge $e_{m + 1}$ exactly if $G_{m} \cup {e_{m + 1}}$ has property $K$ . We analyse the behaviour of this process, focusing mainly on two questions: What can be said about the structure of $G_{N}$ and for which $m$ will $G_{m}$ contain a perfect matching?