Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T08:45:34.766Z Has data issue: false hasContentIssue false
  • English
  • Français

The Strongly Connected Components of 1-in, 1-out

Published online by Cambridge University Press:  12 September 2008

B. Reed  and
Colin McDiarmid
B. Reed
Affiliation:
Universität Bonn
Colin McDiarmid
Affiliation:
Department of Statistics, Oxford University
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider a random digraph Din, out(n) on vertices 1, …, n, where, for each vertex v, we choose at random one of the n possible arcs with head v and one of the n possible arcs with tail v. We show that the expected size of the largest component of Din, out is .

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 3 , September 1992 , pp. 265 - 274
Copyright
Copyright © Cambridge University Press 1992

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Cooper, C. and Frieze, A. M. (1990) The limiting probability that α-in, β-out is strongly connected. J. Comb. Th. B 48 117–134.CrossRefGoogle Scholar
[2]Feller, W. (1968) Introduction to Probability Theory and its Applications, Vol. 1 (3rd edition). Wiley, New York.Google Scholar
[3]Kolchin, V. F. (1986) Random Mappings. Optimization Software, New York.Google Scholar
[4]McDiarmid, C. J. H. (1989) On the method of bounded differences. In: Siemons, J. (editor) Surveys in Combinatorics 1989, London Math. Soc. Lecture Note Series 141. Cambridge University Press.Google Scholar