Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T04:11:23.411Z 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: 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 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.

Information

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 

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