Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650048 | Discrete Mathematics | 2009 | 15 Pages |
Abstract
Let G(n,m) be an undirected random graph with n vertices and m multiedges that may include loops, where each edge is realized by choosing its two vertices independently and uniformly at random with replacement from the set of all n vertices. The random graph G(n,m) is said to be k-orientable, where kâ¥2 is an integer, if there exists an orientation of the edges such that the maximum out-degree is at most k. Let ck=sup{c:G(n,cn) is k-orientable w.h.p.}. We prove that for k large enough, 1â2kexp(âk+1+eâk/4)
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Luc Devroye, Ebrahim Malalla,