The role of graphs with tree structure in some sciences

Document Type : Original Article

Authors

Department of Mathematical Sciences, Yazd University, Yazd, Iran

Abstract

Trees are one of the most basic classes in graphs. They not only play a key role in the theory of graphs and combinatorics, but also in many other fields of mathematics, as well as in other sciences such as biology, chemistry, and computer science. In this article, we review the applications of trees in chemistry, biology, and computers.

Keywords

Main Subjects


[1]  Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math. 29, 2015, no. 4, 2065–2074, DOI 10.1137/140997750. MR3416130
[2] Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math. 29, 2015, no. 4, 2065–2074, DOI 10.1137/140997750. MR3416130
[3]  Joshua Cooper, Bill Kay, and Anton Swifton, Graham’s tree reconstruction conjecture and a Waring-type problem on partitions, J. Comb. 9, 2018, no. 3, 469–488, DOI 10.4310/JOC.2018.v9.n3.a3. MR3809644
[4]  Michael Drmota, Random trees: An interplay between combinatorics and probability, SpringerWienNewYork, Vienna, 2009, DOI 10.1007/978-3-211-75357-6. MR2484382
[5]  Donald E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley, Reading, MA, 1997. Third edition [of MR0286317]. MR3077152
[6] Alexey Markin, On the extremal maximum agreement subtree problem, Discrete Appl. Math. 285,  2020, 612–620, DOI 10.1016/j.dam.2020.07.007. MR4124794
[7]  Daniel M. Martin and Bhalchandra D. Thatte, The maximum agreement subtree problem, Discrete Appl. Math. 161, 2013, no. 13-14, 1805–1817, DOI 10.1016/j.dam.2013.02.037. MR3056987
[8]  Pratik Misra and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree for a given tree shape, SIAM J. Discrete Math. 33, 2019, no. 4, 2316–2325, DOI 10.1137/18M1213695. MR4036089
[9] R. Montgomery, A. Pokrovskiy, and B. Sudakov, A proof of Ringel’s conjecture, Geom. Funct. Anal. 31, 2021, no. 3, 663–720, DOI 10.1007/s00039-021-00576-2. MR4311581
[10]  G. P\' olya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen (German), Acta Math. 68, 1937, no. 1, 145–254, DOI 10.1007/BF02546665. MR1577579
[11]  Robert Sedgewick and Philippe Flajolet, An
 introduction to the analysis of algorithms, Addison-
Wesley-Longman, 1996.
[12] Stephan Wagner and Hua Wang, Introduction to
chemical graph theory, Discrete Mathematics and its
 Applications (Boca Raton), CRC Press, Boca
 Raton, FL, 2019. MR3837106
[13] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69, 1947, 17–20.