The probability that a random multigraph is simple
2009 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 18, no 1-2, 205-225 p.Article in journal (Refereed) Published
Consider a random multigraph G* with given vertex degrees d(1),...,d(n), constructed by the configuration model. We show that, asymptotically for a sequence of such multigraphs with the number of edges 1/2 Sigma(i) d(i) -> infinity, the probability that the multigraph is simple stays away from 0 if and only if Sigma(i) d(i)(2) = O (Sigma(i) d(i)). This was previously known only under extra assumptions on the maximum degree max(i) d(i). We also give an asymptotic formula for this probability, extending previous results by several authors.
Place, publisher, year, edition, pages
2009. Vol. 18, no 1-2, 205-225 p.
Research subject Mathematics
IdentifiersURN: urn:nbn:se:uu:diva-114306DOI: 10.1017/S0963548308009644ISI: 000265047400010OAI: oai:DiVA.org:uu-114306DiVA: diva2:293722