TOPICS
Search

Series-Reduced Tree


SeriesReducedTrees

A series-reduced tree is 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 (Harary and Palmer 1973, pp. 61-62) 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). Harary and Palmer (1973, p. 62, Fig. 3.3.3) illustrate the series-reduced trees on 8 and fewer nodes.

Special cases of series-reduced trees include alkane graphs and star graphs S_n on n>3 nodes.

Series-reduced trees are best known in popular culture due to their appearance in the second blackboard problem in the 1997 film Good Will Hunting, which poses the problem of finding all (10) such trees on 10 nodes.

The numbers of series-reduced planted trees on n=1, 2, ... nodes are 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, ... (OEIS A001678) and the numbers of series-reduced rooted trees are 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, ... (OEIS A001679).

The process of replacing edges e_(ij)e_(jk) adjacent to a degree-2 vertex v_j by a single edges e_(ik) is known as graph smoothing.


See also

Good Will Hunting Problems, Graph Smoothing, Planted Tree, Rooted Tree, Tree

Explore with Wolfram|Alpha

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. Graphical Enumeration. New York: Academic Press, p. 61-62, 1973.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

Subject classifications