Representing non-crossing cuts by phylogenetic trees

Thomas Lange


Phylogenetic trees are representations of the evolutionary descendency of a set of species. In graph-theoretic terms, a phylogenetic tree is a partially labeled tree where unlabeled vertices have at least degree three and labels corresponds to pairwise disjoint subsets of the set of species. A cut of a graph G = (V, E) is defined as bipartition {S, V \ S} of the vertex set V of G. A pair of cuts {S, S}, {T, T} is said to be crossing, if neither S ∩ TS ∩ TS ∩ T nor S ∩ T is empty. In this paper, we show that each set of pairwise non-crossing cuts of a graph G can be represented uniquely by a phylogenetic tree such that the set of species corresponds to the vertex set of G.


pairwise laminar cutset; phylogenetic tree; edge-bipartition

Full Text:




R. Alberich, G. Cardona, F. Rossello, and G. Valiente, An algebraic metric for phylogenetic trees, Appl. Math. Lett. (2009), 1320–1324.

J. Felsenstein, The number of evolutionary trees, Systematic Biology 27 (1) (1978), 27–33.

W.M. Fitch and E. Margoliash, Construction of phylogenetic trees, Science 155 (3760) (1967), 279–284.

C. Flight, How many stemmata?, Manuscripta 34 (2) (1990), 122–128.

L.R. Foulds and R.W. Robinson, Enumeration of binary phylogenetic trees, Combinatorial Mathematics VIII (1981), 187–202.

L.R. Foulds and R.W. Robinson, Enumerating phylogenetic trees with multiple labels, Discrete Math. 72 (1-3) (1988), 129–139.

L. Lovasz, On two minimax theorems in graph, J. Combin. Theory Ser. B 21 (2) (1976), 96–103.

C. Lucet, J-F. Manouvrier and J. Carlier, Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs, Algorithmica 27 (2000), 316–336.

I.P. McWhirter and D.H. Younger, Strong covering of a bipartite graph, J. Lond. Math. Soc. s2-3 (1) (1971), 86–90.

D.F. Robinson and L.R. Foulds, Comparison of phylogenetic trees, Mathematical Biosciences 53 (1-2) (1981), 131–147.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats