The Kőnig graph process. Issue 4 (9th October 2020) - Kamčev, Nina; Krivelevich, Michael; Morrison, Natasha; Sudakov, Benny
Abstract : Say that a graph G has property 𝒦 if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set N : = n 2 and let e 1,   e 2,  …  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  ≥ 0, Gm  + 1 is obtained from Gm by adding the edge e m  + 1 exactly if Gm  ∪ { e m  + 1 } has property 𝒦 . We analyze the behavior of this process, focusing mainly on two questions: What can be said about the structure of GN and for which m will Gm contain a perfect matching?