Metadata only
Date
2020-12Type
- Journal Article
ETH Bibliography
yes
Altmetrics
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 Show more
Publication status
publishedExternal links
Journal / series
Random Structures & AlgorithmsVolume
Pages / Article No.
Publisher
WileySubject
matching; perfect matching; random graph; random process; vertex coverOrganisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin
More
Show all metadata
ETH Bibliography
yes
Altmetrics