# 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** : English

**Publication year** : 2001