ON THE CONNECTIVITY OF GRAPHS GENERATED BY A SUM OF RANDOM MAPPINGS

Authors
JAWORSKI J KARONSKI M
Citation
J. Jaworski et M. Karonski, ON THE CONNECTIVITY OF GRAPHS GENERATED BY A SUM OF RANDOM MAPPINGS, Journal of graph theory, 17(2), 1993, pp. 135-150
Citations number
11
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
Journal of graph theory → ACNP
ISSN journal
03649024
Volume
17
Issue
2
Year of publication
1993
Pages
135 - 150
Database
ISI
SICI code
0364-9024(1993)17:2<135:OTCOGG>2.0.ZU;2-2
Abstract
We consider four models of random directed multigraphs with n labeled vertices of out-degree d. First we establish formal relationships betw een our models with respect to exact and asymptotic (as n --> infinity ) probabilities of possessing a graph monotone property. We also study the asymptotic behavior of the strength of connectivity of the underl ying simple graphs when d = o(n).