Series-Reduced Tree
A tree in which all nodes have degree other than 2 (in other words, no node merely allows a single edge to "pass through"). Series-reduced
trees are also called homeomorphically irreducible or topological trees (Bergeron
et al. 1998). The numbers of series-reduced trees with 1, 2, ... nodes are
1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, ... (OEIS A000014).
The numbers of series-reduced planted trees are 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, ... (OEIS A001678).
The numbers of series-reduced rooted trees are 1,
1, 0, 2, 2, 4, 6, 12, 20, 39, 71, ... (OEIS A001679).
SEE ALSO: Planted Tree,
Rooted
Tree,
Tree
REFERENCES:
Bergeron, F.; Leroux, P.; and Labelle, G. Combinatorial Species and Tree-Like Structures. Cambridge, England: Cambridge University
Press, pp. 188, 283-284, 291, and 337, 1998.
Cameron, P. J. "Some Treelike Objects." Quart. J. Math. Oxford 38,
155-183, 1987.
Finch, S. R. §5.6 in Mathematical
Constants. Cambridge, England: Cambridge University Press, 2003.
Harary, F. Graph
Theory. Reading, MA: Addison-Wesley, p. 232, 1994.
Harary, F. and Palmer, E. M. "Probability that a Point of a Tree Is Fixed."
Math. Proc. Camb. Phil. Soc. 85, 407-415, 1979.
Harary, F. and Prins, G. "The Number of Homeomorphically Irreducible Trees,
and Other Species." Acta Math. 101, 141-162, 1959.
Harary, F.; Robinson, R. W. and Schwenk, A. J. "Twenty- Step Algorithm for Determining the Asymptotic Number of Trees of Various Species." J. Austral.
Math. Soc., Ser. A 20, 483-503, 1975.
Sloane, N. J. A. Sequences A000014/M0320, A001678/M0768, and A001679/M0327
in "The On-Line Encyclopedia of Integer Sequences."
Referenced on Wolfram|Alpha:
Series-Reduced Tree
CITE THIS AS:
Weisstein, Eric W. "Series-Reduced Tree."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Series-ReducedTree.html
Contact the MathWorld Team
acyclic graph