d-connectivity of the random graph with restricted budget

2022/08/08 by Lyuben Lichev, Lichev, Lyuben
Computer Science · Mathematics · #05C40 #05C80 #Combinatorics (math.CO) #Distributed systems and fault tolerance #FOS: Mathematics #Optimization and Search Problems #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2208.04111

openalex publication_date 2022/08/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short note, we consider a graph process recently introduced by Frieze, Krivelevich and Michaeli. In their model, the edges of the complete graph K_n are ordered uniformly at random and are then revealed consecutively to a player called Builder. At every round, Builder must decide if they accept the edge proposed at this round or not. We prove that, for every d≥ 2, Builder can construct a spanning d-connected graph after (1+o(1))nlog n/2 rounds by accepting (1+o(1))dn/2 edges with probability converging to 1 as n→ ∞. This settles a conjecture of Frieze, Krivelevich and Michaeli.

Related

• Graph factors and powers of Hamilton cycles in the budget-constrained random graph process
• Fast construction on a restricted budget
• Building graphs with high minimum degree on a budget
• Multi-cyclic graphs in the random graph process with restricted budget
• Minimum degree k and k-connectedness usually arrive together