TOPICS
Search

Labeled Tree


LabeledTrees

A tree with its nodes labeled. The number of labeled trees on n nodes is n^(n-2), the first few values of which are 1, 1, 3, 16, 125, 1296, ... (OEIS A000272). Cayley (1889) provided the first proof of the number of labeled trees (Skiena 1990, p. 151), and a constructive proof was subsequently provided by Prüfer (1918). Prüfer's result gives an encoding for labeled trees known as Prüfer code (indicated underneath the trees above, where the trees are depicted using an embedding with root at the node labeled 1).

The probability that a random labeled tree is centered is asymptotically equal to 1/2 (Szekeres 1983; Skiena 1990, p. 167).


See also

Labeled Graph, Prüfer Code, Tree

Explore with Wolfram|Alpha

References

Biggs, N. L.; Lloyd, E. K.; and Wilson, R. J. Graph Theory 1736-1936. Oxford, England: Oxford University Press, p. 51, 1976.Cayley, A. "A Theorem on Trees." Quart. J. Math. 23, 376-378, 1889.Prüfer, H. "Neuer Beweis eines Satzes über Permutationen." Arch. Math. Phys. 27, 742-744, 1918.Riordan, J. An Introduction to Combinatorial Analysis. New York: Wiley, p. 128, 1980.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A000272/M3027 in "The On-Line Encyclopedia of Integer Sequences."Szekeres, G. Distribution of Labeled Trees by Diameter. New York: Springer-Verlag, pp. 392-397, 1983.van Lint, J. H. and Wilson, R. M. A Course in Combinatorics. New York: Cambridge University Press, 1992.

Referenced on Wolfram|Alpha

Labeled Tree

Cite this as:

Weisstein, Eric W. "Labeled Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LabeledTree.html

Subject classifications