The Kőnig graph process

Abstract

Say that a graph G has property urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0001 if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0002 and let e1, e2, … eN be a uniformly random ordering of the edges of Kn, with n an even integer. Let G0 be the empty graph on n vertices. For m ≥ 0, Gm + 1 is obtained from Gm by adding the edge em + 1 exactly if Gm ∪ {em + 1} has property urn:x-wiley:rsa:media:rsa20969:rsa20969-math-0003. 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? © 2020 Wiley Periodicals