The Kőnig graph process
METADATA ONLY
Loading...
Author / Producer
Date
2020-12
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
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
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
57 (4)
Pages / Article No.
1272 - 1302
Publisher
Wiley
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
matching; perfect matching; random graph; random process; vertex cover
Organisational unit
03993 - Sudakov, Benjamin / Sudakov, Benjamin