Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-09T21:32:42.532Z Has data issue: false hasContentIssue false
  • English
  • Français

SOME PROPERTIES OF BINARY SERIES-PARALLEL GRAPHS

Published online by Cambridge University Press:  27 June 2014

Hosam M. Mahmoud
Hosam M. Mahmoud*
Affiliation:
Department of Statistics, The George Washington University, Washington, DC 20052, USA E-mail: hosam@gwu.edu
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

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

1.Athreya, K. & Karlin, S. (1968). Embedding of urn schemes into continuous time Markov branching process and related limit theorems. Ann. Math. Stat. 39: 1801–1817.CrossRefGoogle Scholar
2.Bernasconi, N., Panagiotou, K. & Steger, A. (2008). On the degree sequences of random outerplanar and series-parallel graphs. Lect. Notes Comput. Sci. 5171: 303–316.CrossRefGoogle Scholar
3.Devroye, L. (1991). Limit laws for local counters in random binary search trees. Random Struct. Algorithms 2: 303–316.CrossRefGoogle Scholar
4.Drmota, M., Giménez, O. & Noy, M. (2010). Vertices of given degree in series-parallel graphs. Random Struct. Algorithms 36: 273–314.CrossRefGoogle Scholar
5.Hambly, B. & Jordan, J. (2004). A random hierarchical lattice: the series-parallel graph and its properties. Adv. Appl. Probab. 36: 824–838.CrossRefGoogle Scholar
6.Janson, S. (2004). Functional limit theorems for multitype branching processes and generalized Pólya urns. Stoch. Process. Appl. 110: 177–245.CrossRefGoogle Scholar
7.Mahmoud, H. (2013). Some node degree properties of series-parallel graphs evolving under a stochastic growth model. Probab. Eng. Inf. Sci. 27: 297–307.CrossRefGoogle Scholar