DocumentCode
1410000
Title
On the diameter of a class of random graphs
Author
Philips, Thomas K. ; Towsley, Donald F. ; Wolf, Jack K.
Author_Institution
IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
Volume
36
Issue
2
fYear
1990
fDate
3/1/1990 12:00:00 AM
Firstpage
285
Lastpage
288
Abstract
The diameter of a class of random directed graphs in which the outdegree of each vertex is constrained to be exactly k is examined. Vertices connect themselves to k other distinct vertices with outwardly directed edges, all possible sets of k vertices being chosen with equal probability. It is shown that the diameter of such a random graph almost surely takes on only one of two values
Keywords
directed graphs; diameter; random directed graphs; Magnetic recording; Tree graphs; Upper bound;
fLanguage
English
Journal_Title
Information Theory, IEEE Transactions on
Publisher
ieee
ISSN
0018-9448
Type
jour
DOI
10.1109/18.52474
Filename
52474
Link To Document