Premium
Weight of a link in a shortest path tree and the Dedekind Eta function
Author(s) -
Van Mieghem Piet
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20299
Subject(s) - mathematics , combinatorics , tree (set theory) , exponential function , shortest path problem , random graph , function (biology) , generating function , dedekind cut , discrete mathematics , graph , mathematical analysis , evolutionary biology , biology
The weight of a randomly chosen link in the shortest path tree on the complete graph with exponential i.i.d. link weights is studied. The corresponding exact probability generating function and the asymptotic law are derived. As a remarkable coincidence, this asymptotic law is precisely the same as the distribution of the cost of one “job” in the random assignment problem. We also show that the asymptotic (scaled) maximum interattachment time to that shortest path tree, which is a uniform recursive tree, equals the square of the Dedekind Eta function, a central function in modular forms, elliptic functions, and the theory of partitions. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010