科研之友
微信
新浪微博
Facebook
分享链接
摘要
Over 50 years ago, Erdos and Gallai conjectured that the edges of every graph on n vertices can be decomposed into O(n) cycles and edges. Among other results, Conlon, Fox and Sudakov recently proved that this holds for the random graph G(n, p) with probability approaching 1 as n -> infinity. In this paper we show that for most edge probabilities G(n, p) can be decomposed into a union of n/4 + np/2 + o(n) cycles and edges w.h.p. This result is asymptotically tight.
- 出版日期2015-11
