Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-07T21:29:38.410Z 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: kuba@dmg.tuwien.ac.at)
STEPHAN WAGNER
Affiliation:
Department of Mathematical Sciences, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa (e-mail: swagner@sun.ac.za)
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.

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.

Information

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

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