Bastert, Oliver; Rockmore, Dan; Stadler, Peter F.; Tinhofer, Gottfried

Some Properties of Robinson Graphs

Electronic source: (local)
[PDF](374 k) [Postscript] (270k)
Preprints series :
Techn. Univ. München, Fak. f. Math., Report (Blauer Bericht) TUM M0101, p. 1-24
Mathematics Subject Classification :
05C05 [ Combinatorics, Graph theory, Trees]
05C90 [ Combinatorics, Graph theory, Applications]
Abstract :
Robinson graphs are configuration graphs over sets of phylogenetic trees. Their neighbor relation is given by all possible crossovers along inner edges of these trees. We show that Robinson graphs generate coherent algebras the cell partition of which equals the automorphism partition. Each cell consists of all phylogenetic trees having isomorphic inner trees (induced by the non-leaves).
Keywords :
phylogenetic trees; Robinson graphs; coherent algebras; cell partition
Language :
Publication year :