dc.contributor.author | Koerts, Hidde | |
dc.date.accessioned | 2022-12-20 20:57:19 (GMT) | |
dc.date.available | 2022-12-20 20:57:19 (GMT) | |
dc.date.issued | 2022-12-20 | |
dc.date.submitted | 2022-12-14 | |
dc.identifier.uri | http://hdl.handle.net/10012/18976 | |
dc.description.abstract | The semi-random graph process is a single-player graph game where the player is initially
presented an edgeless graph with n vertices. In each round, the player is offered a vertex
u uniformly at random and subsequently chooses a second vertex v deterministically ac-
cording to some strategy, and adds edge uv to the graph. The objective for the player is
then to ensure that the graph fulfils some specified property as fast as possible.
We investigate the properties of being k-connected and containing a k-factor. We settle
the open case for 2-connectedness by showing that the player has a strategy to construct a
2-connected graph asymptotically almost surely in (ln 2+ln(ln 2+1)+o(1))n rounds, which
matches a known lower bound asymptotically. We also provide a strategy for building a
k-factor asymptotically almost surely in (β + 10^−5)n rounds, where β is derived from the
solution of a system of differential equations.
Additionally, we consider a variant that was recently suggested by Wormald where the
player chooses the first vertex and the second vertex is chosen uniformly at random. We
show that the bounds for k-connectedness for the traditional setting are also tight for this
variant. | en |
dc.language.iso | en | en |
dc.publisher | University of Waterloo | en |
dc.subject | semi-random graph process | en |
dc.subject | k-factor | en |
dc.subject | k-connectedness | en |
dc.subject | random graph theory | en |
dc.subject | pre-positional semi-random graph process | en |
dc.subject | post-positional semi-random graph process | en |
dc.title | k-Connectedness and k-Factors in the Semi-Random Graph Process | en |
dc.type | Master Thesis | en |
dc.pending | false | |
uws-etd.degree.department | Combinatorics and Optimization | en |
uws-etd.degree.discipline | Combinatorics and Optimization | en |
uws-etd.degree.grantor | University of Waterloo | en |
uws-etd.degree | Master of Mathematics | en |
uws-etd.embargo.terms | 0 | en |
uws.contributor.advisor | Gao, Jane | |
uws.contributor.affiliation1 | Faculty of Mathematics | en |
uws.published.city | Waterloo | en |
uws.published.country | Canada | en |
uws.published.province | Ontario | en |
uws.typeOfResource | Text | en |
uws.peerReviewStatus | Unreviewed | en |
uws.scholarLevel | Graduate | en |