Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-25T01:33:44.706Z Has data issue: false hasContentIssue false
  • English
  • Français

SOME NODE DEGREE PROPERTIES OF SERIES–PARALLEL GRAPHS EVOLVING UNDER A STOCHASTIC GROWTH MODEL

Published online by Cambridge University Press:  28 March 2013

Hosam M. Mahmoud
Hosam M. Mahmoud*
Affiliation:
Department of Statistics, The George Washington University, Washington, D.C. 20052, U.S.A. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a natural growth model for directed series-parallel (SP) graphs and look at some of the graph properties under this stochastic model. Specifically, we look at the degrees of certain types of nodes in the random SP graph. We examine the degree of a pole and will find its exact distribution, given by a probability formula with alternating signs. We also prove that, for a fixed value s, the number of nodes of outdegree 1, …, s asymptotically has a joint multivariate normal distribution. Pólya urns will systematically provide a working tool.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 27 , Issue 3 , July 2013 , pp. 297 - 307
Copyright
Copyright © Cambridge University Press 2013 

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. The Annals of Mathematical Statistics 39: 1801–1817.CrossRefGoogle Scholar
2.Bernasconi, N., Panagiotou, K., & Steger, A. (2008). On the degree sequences of random outerplanar and series-parallel graphs. Lecture Notes in Computer Science 5171: 303–316.CrossRefGoogle Scholar
3.De Moivre, A. (1712). The Doctrine of Chances. London: Millar. Reprinted in 1967 by Chelsea, New York.Google Scholar
4.Drmota, M., Giménez, O., & Noy, M. (2010). Vertices of given degree in series-parallel graphs. Random Structures & Algorithms 36, 273–314.CrossRefGoogle Scholar
5.Hambly, B. & Jordan, J. (2004). A random hierarchical lattice: the series-parallel graph and its properties. Advances in Applied Probability 36: 824–838.CrossRefGoogle Scholar
6.Morcrette, B. & Mahmoud, H. (2012). Exactly solvable balanced tenable urns with random entries via the analytic methodology. Discrete Mathematics and Theoretical Computer Science proc., 219–232.CrossRefGoogle Scholar
7.Smythe, R. (1996). Central limit theorems for urn models. Stochastic Processes and Their Applications 65: 115–137.CrossRefGoogle Scholar