Asymptotically optimal time-and-budget conjecture for k-connectivity
Asymptotically optimal time-and-budget conjecture for k-connectivity
Let be a positive integer, let , and let a -strategy of Builder be a strategy that observes at most arriving edges and purchases at most of them. A graph is -connected if it remains connected after deletion of any set of fewer than vertices. Asymptotically optimal time-and-budget conjecture for -connectivity. If
then there exists a -strategy of Builder such that
The claim is stated as an open extension of the established construction for minimum degree: allowing asymptotically optimal time and budget should suffice to construct a -connected graph. The source notes that the case is trivially true.
Sources & referencesView supporting material
Primary source
Alan Frieze, Michael Krivelevich and Peleg Michaeli, “Fast construction on a restricted budget”, arXiv:2207.07251 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.