The Kőnig graph process

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

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Say that a graph G has property (Formula presented.) if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. Set (Formula presented.) 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 (Formula presented.). 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?.

Original languageEnglish
Pages (from-to)1272-1302
Number of pages31
JournalRandom Structures & Algorithms
Volume57
Issue number4
DOIs
Publication statusPublished - 1 Dec 2020

Keywords

  • matching
  • perfect matching
  • random graph
  • random process
  • vertex cover

Cite this