title: Unicyclic networks: compatibility and enumeration.
abstract: Graphs obtained from a binary leaf labeled ("phylogenetic") tree by adding an edge so as to introduce a cycle provide a useful representation of hybrid evolution in molecular evolutionary biology. This class of graphs (which we call "unicyclic networks") also has some attractive combinatorial properties, which we present. We characterize when a set of binary phylogenetic trees is displayed by a unicyclic network in terms of tree rearrangement operations. This leads to a triple-wise compatibility theorem and a simple, fast algorithm to determine 1-cycle compatibility. We also use generating function techniques to provide closed-form expressions that enumerate unicyclic networks with specified or unspecified cycle length, and we provide an extension to enumerate a class of multicyclic networks.
authors.affiliation: Biomathematics Research Centre, Department of Mathematics and Statistics, University of Canterbury, Private Bag 4800, Christchurch, New Zealand. c.semple@math.canterbury.ac.nz
authors.forename: Charles
authors.initials: C
authors.lastname: Semple
authors.forename: Mike
authors.initials: M
authors.lastname: Steel
mesh_terms: D000465:Algorithms; D005075:Biological Evolution; D003198:Computer Simulation; D019143:Evolution, Molecular; D005828:Genetics, Population; D008957:Models, Genetic; D010802:Phylogeny; D011995:Recombination, Genetic / Q000235:genetics; D015398:Signal Transduction / Q000235:genetics*