Quasi-median graphs from sets of partitions

H.-J. Bandelt, K. T. Huber, V. Moulton

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


In studies of molecular evolution, one is typically confronted with the task of inferring a phylogenetic tree from a set X of sequences of length n over a finite alphabet ?. For studies that invoke parsimony, it has been found helpful to consider the quasi-median graph generated by X in the Hamming graph ?n. Although a great deal is already known about quasi-median graphs (and their algebraic counterparts), little is known about the quasi-median generation in ?n starting from a set X of vertices. We describe the vertices of the quasi-median graph generated by X in terms of the coordinatewise partitions of X. In particular, we clarify when the generated quasi-median graph is the so-called relation graph associated with X. This immediately characterizes the instances where either a block graph or the total Hamming graph is generated.
Original languageEnglish
Pages (from-to)23-35
Number of pages13
JournalDiscrete Applied Mathematics
Issue number1-3
Publication statusPublished - 15 Oct 2002

Cite this