Naslov
The Kőnig graph process

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

Izvornik
Random Structures &amp ; Algorithms (1042-9832) 57 (2020), 4; 1272-1302

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Random process

Sažetak
Say that a graphGhas property K if the size of its maximum matching is equal to the order of a minimal vertex cover. We study the following process. SetN:=(n2) and lete(1), e(2), horizontal ellipsis e(N)be a uniformly random ordering of the edges ofK(n), withnan even integer. LetG0 be the empty graph onnvertices. Form >= 0, Gm + 1 is obtained fromGmby adding the edgee(m + 1)exactly ifGm ? {;e(m + 1)}; has property K. We analyze the behavior of this process, focusing mainly on two questions: What can be said about the structure ofGNand for which m will Gm contain a perfect matching?

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA