Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-30T01:55:16.875Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Difference of Expected Lengths of Minimum Spanning Trees

Published online by Cambridge University Press:  01 May 2009

WENBO V. LI  and
XINYI ZHANG
WENBO V. LI
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark DE 19716, USA (e-mail: [email protected], [email protected])
XINYI ZHANG
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark DE 19716, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

An exact formula for the expected length of the minimum spanning tree of a connected graph, with independent and identical edge distribution, is given, which generalizes Steele's formula in the uniform case. For a complete graph, the difference of expected lengths between exponential distribution, with rate one, and uniform distribution on the interval (0, 1) is shown to be positive and of rate ζ(3)/n. For wheel graphs, precise values of expected lengths are given via calculations of the associated Tutte polynomials.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 3 , May 2009 , pp. 423 - 434
Copyright
Copyright © Cambridge University Press 2008

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]Avram, F. and Bertsimas, D. (1992) The minimum spanning tree constant in geometric probability and under the independent model: A unified approach. Ann. Appl. Probab. 2 113–130.CrossRefGoogle Scholar
[2]Benedict, C. P. (1969) On self-dualisms in graphs and networks. PhD dissertation, University of Waterloo, Waterloo, Ontario, Canada.Google Scholar
[3]Benjamin, A. T. and Yerger, C. R. (2006) Combinatorial interpretations of spanning tree identities. Bull. Inst. Combin. Appl. 47 37–42.Google Scholar
[4]Beveridge, A., Frieze, A. and McDiarmid, C. (1998) Minimum length spanning trees in regular graphs. Combinatorica 18 311–333.CrossRefGoogle Scholar
[5]Bollobás, B. (2001) Random Graphs, 2nd edn, Cambridge University Press.CrossRefGoogle Scholar
[6]Bollobás, B. (2002) Modern Graph Theory, Springer.Google Scholar
[7]Cayley, A. (1889) A theorem on trees. Quart. J. Pure Appl. Math. 23 376–378.Google Scholar
[8]Fill, J. A. and Steele, J. M. (2005) Exact expectations of minimal spanning trees for graphs with random edge weights. Stein's method and applications, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., Singapore University Press, Singapore, 5169–180.Google Scholar
[9]Flaxman, A. D. (2007) The lower tail of the random minimum spanning tree. Electron. J. Combin. 14 #3.CrossRefGoogle Scholar
[10]Frieze, A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47–56.CrossRefGoogle Scholar
[11]Frieze, A. M. and McDiarmid, C. J. H. (1989) On random minimum length spanning trees. Combinatorica 9 363–374.CrossRefGoogle Scholar
[12]Frieze, A. M., Ruszinkó, M. and Thoma, L. (2000) A note on random minimum length spanning trees. Electron. J. Combin. 7 #5.CrossRefGoogle Scholar
[13]Gamarnik, D. (2005) The expected value of random minimal length spanning tree of a complete graph. In Proc. 16th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 700–704.Google Scholar
[14]Hutson, K. and Lewis, T. M. (2007) The expected length of a minimum spanning tree of a cylinder graph. Combin. Probab. Comput. 16 63–83.CrossRefGoogle Scholar
[15]Janson, S. (1993) Multicyclic components in a random graph process. Random Struct. Alg. 4 71–84.CrossRefGoogle Scholar
[16]Janson, S. (1995) The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph. Random Struct. Alg. 7 337–355.CrossRefGoogle Scholar
[17]McDiarmid, C. (1989) On the method of bounded differences. In Surveys in Combinatorics, Vol. 141 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 148–188.Google Scholar
[18]Myers, B. R. (1971) Number of spanning trees in a wheel. IEEE Trans. Circuit Theory CT-18 280–282.CrossRefGoogle Scholar
[19]Penrose, M. (1998) Random minimum spanning tree and percolation on the n-cube. Random Struct. Alg. 12 63–82.3.0.CO;2-R>CrossRefGoogle Scholar
[20]Sedlacek, J. (1970) On the skeletons of a graph or digraph. In Proc. Calgary International Conference on Combinatorial Structures and their Applications, Gordon and Breach, pp. 387–391.Google Scholar
[21]Smith, C. A. B. and Tutte, W. T. (1950) A class of self-dual maps. Canad. J. Math. 2 179–196.CrossRefGoogle Scholar
[22]Steele, J. M. (1987) On Frieze's ζ(3) limit for lengths of minimal spanning trees. Discrete Appl. Math. 18 99–103.CrossRefGoogle Scholar
[23]Steele, J. M. (2002) Minimum spanning trees for graphs with random edge lengths. In Mathematics and Computer Science II: Algorithms, Trees, Combinatorics and Probabilities, Birkhäuser, pp. 223–245.CrossRefGoogle Scholar
[24]Tutte, W. T. (1950) Squaring the square. Canad. J. Math. 2 197–209.CrossRefGoogle Scholar
[25]Welsh, D. (1999) The Tutte polynomial. Random Struct. Alg. 15 210–228.3.0.CO;2-R>CrossRefGoogle Scholar