Hostname: page-component-586b7cd67f-gb8f7 Total loading time: 0 Render date: 2024-11-29T15:22:13.299Z Has data issue: false hasContentIssue false
  • English
  • Français

Deterministic Edge Weights in Increasing Tree Families

Published online by Cambridge University Press:  22 June 2009

MARKUS KUBA  and
STEPHAN WAGNER
MARKUS KUBA
Affiliation:
Institut für Diskrete Mathematik und Geometrie, Technische Universität Wien, Wiedner Hauptstr. 8-10/104, 1040 Wien, Austria (e-mail: [email protected])
STEPHAN WAGNER
Affiliation:
Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this work we study edge weights for two specific families of increasing trees, which include binary increasing trees and plane-oriented recursive trees as special instances, where plane-oriented recursive trees serve as a combinatorial model of scale-free random trees given by the m = 1 case of the Barabási–Albert model. An edge e = (k, l), connecting the nodes labelled k and l, respectively, in an increasing tree, is associated with the weight we = |k − l|. We are interested in the distribution of the number of edges with a fixed edge weight j in a random generalized plane-oriented recursive tree or random d-ary increasing tree. We provide exact formulas for expectation and variance and prove a normal limit law for this quantity. A combinatorial approach is also presented and applied to a related parameter, the maximum edge weight.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 1 , January 2010 , pp. 99 - 119
Copyright
Copyright © Cambridge University Press 2009

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]Albert, R., Jeong, H. and Barabási, A.-L. (1999) The diameter of the world wide web. Nature 401 130–131.CrossRefGoogle Scholar
[2]Barabási, A.-L. and Albert, R. (1999) Emergence of scaling in random networks. Science 286 509–512.CrossRefGoogle ScholarPubMed
[3]Barbour, A. D. and Eagleson, G. K. (1985) Multiple comparisons and sums of dissociated random variables. Adv. Appl. Probab. 17 147–162.CrossRefGoogle Scholar
[4]Barbour, A. D., Karoński, M. and Ruciński, A. (1989) A central limit theorem for decomposable random variables with applications to random graphs. J. Combin. Theory Ser. B 47 125–145.CrossRefGoogle Scholar
[5]Bergeron, F., Flajolet, P. and Salvy, B. (1992) Varieties of Increasing Trees, Vol. 581 of Lecture Notes in Computer Science, Springer, pp. 24–48.Google Scholar
[6]Bergeron, F., Labelle, G. and Leroux, P. (1998) Combinatorial Species and Tree-Like Structures, Vol. 67 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge.Google Scholar
[7]Bollobás, B. and Riordan, O. (2003) Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks (Bornholdt, S. and Schuster, H. G., eds), Wiley-VCH, Weinheim, pp. 1–34.Google Scholar
[8]Bollobás, B. and Riordan, O. (2004) Shortest paths and load scaling in scale-free trees. Phys. Rev. E 69 #036114.CrossRefGoogle ScholarPubMed
[9]Dobrow, R. and Smythe, R. (1996) Poisson approximations for functionals of random trees. Random Struct. Alg. 9 79–92.3.0.CO;2-8>CrossRefGoogle Scholar
[10]Hoare, C. A. R. (1962) Quicksort. Comput. J. 5 1015.CrossRefGoogle Scholar
[11]Hwang, H.-K. (1998) On convergence rates in the central limit theorems for combinatorial structures. Europ. J. Combin. 19 329–343.CrossRefGoogle Scholar
[12]Janson, S. (2005) Asymptotic degree distribution in random recursive trees. Random Struct. Alg. 26 69–83.CrossRefGoogle Scholar
[13]Kuba, M. and Panholzer, A. (2008) On edge-weighted recursive trees and inversions in random permutations. Discrete Math. 308 529–540.CrossRefGoogle Scholar
[14]Panholzer, A. and Prodinger, H. (2007) The level of nodes in increasing trees revisited. Random Struct. Alg. 31 203–226.Google Scholar
[15]Vitter, J. and Flajolet, P. (1990) Average Case Analysis of Algorithms and Data Structures. In Handbook of Theoretical Computer Science, Elsevier, Amsterdam, pp. 431–524.Google Scholar