Perfect matchings in random graphs with prescribed minimal degree
Perfect matchings in random graphs with prescribed minimal degree
复制标题
DOI：
10.1007/978-3-0348-7915-6_11
复制
发表时间：
2003-01
期刊：
影响因子：
--
通讯作者：
A. Frieze;B. Pittel
中科院分区：
文献类型：
--
作者：
A. Frieze;B. Pittel
We consider the existence of perfect matchings in random graphs with n vertices (or n + n vertices in the bipartite case) and m random edges, subject to a lower bound on minimum vertex degree. A random bipartite graph without isolated vertices and m n edges with high probability (whp) has a perfect matching iff the average vertex degree ishowever slow. A random graph with minimum degree at least two whp has a matching that matches all the vertices except “odd-man-out” vertices, one per each isolated cycle of odd length, and one for the remaining vertex set if its cardinality is odd. So, for n even, whp the random graph has a perfect matching if it does not have isolated odd cycles.
