Article contents
SOME PROPERTIES OF BINARY SERIES-PARALLEL GRAPHS
Published online by Cambridge University Press: 27 June 2014
Abstract
We introduce an incremental growth model for directed binary series-parallel (SP) graphs. The vertices of a directed binary SP graphs can only have outdgrees 1 or 2. We show that the number of vertices of outdegree 1 have a normal distribution (so, necessarily, the vertices of outdegree 2 have a normal distribution, too). Furthermore, we study the average length of a random walk between the poles of the graph. The asymptotic equivalent of the latter property includes the golden ratio. Pólya urns will systematically provide a coding method to initiate the studies.
- Type
- Research Article
- Information
- Probability in the Engineering and Informational Sciences , Volume 28 , Issue 4 , October 2014 , pp. 565 - 572
- Copyright
- Copyright © Cambridge University Press 2014
References
- 4
- Cited by