Representing non-crossing cuts by phylogenetic trees

Abstract

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 ∩ T, S ∩ T, S ∩ 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.