Even-degeneracy of a random graph
Even-degeneracy of a random graph
A graph is even-degenerate if one can iteratively remove a vertex of even degree at each step until at most one edge remains. Recently, Janzer and Yip showed that the Erd\H{o}s--Renyi random graph $G(n,1/2)$ is even-degenerate with high probability, and asked whether an analogous result holds for any general $G(n,p)$. In this paper, we answer this question for any constant $p\in (0,1)$ in affirmation by proving that $G(n,p)$ is even-degenerate with high probability.
Ting-Wei Chao、Dingding Dong、Zixuan Xu
数学
Ting-Wei Chao,Dingding Dong,Zixuan Xu.Even-degeneracy of a random graph[EB/OL].(2025-06-01)[2025-07-01].https://arxiv.org/abs/2506.01021.点此复制
评论