Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-10T14:37:21.175Z 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: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 

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.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