On the connectivity of randomm-orientable graphs and digraphs |
| |
| Authors: | T I Fenner A M Frieze |
| |
| Institution: | (1) Dept. of Computer Science Birkbeck College, University of London, WC1E 7HX London, England;(2) Dept. of Computer Science and Statistics, Queen Mary College, E1 4NS London, England |
| |
| Abstract: | We consider graphs and digraphs obtained by randomly generating a prescribed number of arcs incident at each vertex.
We analyse their almost certain connectivity and apply these results to the expected value of random minimum length spanning
trees and arborescences.
We also examine the relationship between our results and certain results of Erdős and Rényi. |
| |
| Keywords: | 05 C 40 60 C 05 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
