|国家预印本平台
首页|Dirac's theorem for random regular graphs

Dirac's theorem for random regular graphs

Dirac's theorem for random regular graphs

来源:Arxiv_logoArxiv
英文摘要

We prove a `resilience' version of Dirac's theorem in the setting of random regular graphs. More precisely, we show that, whenever $d$ is sufficiently large compared to $\varepsilon>0$, a.a.s. the following holds: let $G'$ be any subgraph of the random $n$-vertex $d$-regular graph $G_{n,d}$ with minimum degree at least $(1/2+\varepsilon)d$. Then $G'$ is Hamiltonian. This proves a conjecture of Ben-Shimon, Krivelevich and Sudakov. Our result is best possible: firstly, the condition that $d$ is large cannot be omitted, and secondly, the minimum degree bound cannot be improved.

Daniela K¨1hn、Deryk Osthus、Padraig Condon、Alberto Espuny D¨aaz、Ant¨?nio Gir?o

数学

Daniela K¨1hn,Deryk Osthus,Padraig Condon,Alberto Espuny D¨aaz,Ant¨?nio Gir?o.Dirac's theorem for random regular graphs[EB/OL].(2019-03-12)[2025-08-10].https://arxiv.org/abs/1903.05052.点此复制

评论