Hamiltonicity threshold conjecture for randomly perturbed directed graphs
Hamiltonicity threshold conjecture for randomly perturbed directed graphs
Let be a directed graph on vertices with minimum semidegree , and let be the binomial random digraph obtained by adding each possible directed edge independently with probability . Let , where .
Directed Hamiltonicity threshold conjecture. The -threshold for Hamiltonicity in randomly perturbed directed graphs is .
This extends the paper's threshold questions from graphs to directed graphs in the critical regime below semidegree . The extension of the corresponding graph theorem to digraphs is stated to remain open.
Sources & referencesView supporting material
Primary source
Alberto Espuny Díaz and Richarlotte Valérà Razafindravola, “How many random edges make an almost-Dirac graph Hamiltonian?”, arXiv:2410.14447 (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.