|国家预印本平台
首页|Even-degeneracy of a random graph

Even-degeneracy of a random graph

Even-degeneracy of a random graph

来源:Arxiv_logoArxiv
英文摘要

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.点此复制

评论