---
OA_place: repository
OA_type: green
_id: '19018'
abstract:
- lang: eng
  text: "The online semi-random graph process is a one-player game which starts with
    the empty graph on n vertices. At every round, a player (called Builder) is presented
    with a vertex v chosen uniformly at random and independently from previous rounds,
    and constructs an edge of their choice that is incident to v. Inspired by recent
    advances on the semi-random graph process, we define a family of generalized online
    semi-random models.\r\nWe analyse a particular instance that shares similar features
    with the original semi-random graph process and determine the hitting times of
    the classical graph properties minimum degree k,k-connectivity, containment of
    a perfect matching, a Hamiltonian cycle and an \r\nH-factor for a fixed graph
    H possessing an additional tree-like property. Along the way, we derive a few
    consequences of the famous Aldous-Broder algorithm that may be of independent
    interest."
acknowledgement: We are grateful to Dieter Mitsche for related discussions and to
  several anonymous referees for multiple useful comments.
article_number: '104120'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sofiya
  full_name: Burova, Sofiya
  last_name: Burova
- first_name: Lyuben
  full_name: Lichev, Lyuben
  id: 9aa8388e-d003-11ee-8458-c4c1d7447977
  last_name: Lichev
citation:
  ama: Burova S, Lichev L. The semi-random tree process. <i>European Journal of Combinatorics</i>.
    2025;126. doi:<a href="https://doi.org/10.1016/j.ejc.2025.104120">10.1016/j.ejc.2025.104120</a>
  apa: Burova, S., &#38; Lichev, L. (2025). The semi-random tree process. <i>European
    Journal of Combinatorics</i>. Elsevier. <a href="https://doi.org/10.1016/j.ejc.2025.104120">https://doi.org/10.1016/j.ejc.2025.104120</a>
  chicago: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” <i>European
    Journal of Combinatorics</i>. Elsevier, 2025. <a href="https://doi.org/10.1016/j.ejc.2025.104120">https://doi.org/10.1016/j.ejc.2025.104120</a>.
  ieee: S. Burova and L. Lichev, “The semi-random tree process,” <i>European Journal
    of Combinatorics</i>, vol. 126. Elsevier, 2025.
  ista: Burova S, Lichev L. 2025. The semi-random tree process. European Journal of
    Combinatorics. 126, 104120.
  mla: Burova, Sofiya, and Lyuben Lichev. “The Semi-Random Tree Process.” <i>European
    Journal of Combinatorics</i>, vol. 126, 104120, Elsevier, 2025, doi:<a href="https://doi.org/10.1016/j.ejc.2025.104120">10.1016/j.ejc.2025.104120</a>.
  short: S. Burova, L. Lichev, European Journal of Combinatorics 126 (2025).
date_created: 2025-02-10T09:00:53Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-09-30T10:28:42Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104120
external_id:
  arxiv:
  - '2204.07376 '
  isi:
  - '001420659400001'
intvolume: '       126'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2204.07376
month: '05'
oa: 1
oa_version: Preprint
publication: European Journal of Combinatorics
publication_identifier:
  issn:
  - 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: The semi-random tree process
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 126
year: '2025'
...