The relation graph Original Research Article

Given a set R of distinct, non-trivial partitions of a finite set, we define the relation graph GR of R. In case R consists only of bipartitions, GR is the well-known Buneman graph, a median graph that has applications in the area of phylogenetic analysis. Here we consider properties of the relation graph for general sets of partitions and, in particular, we see that it mimics the behaviour of the Buneman graph by proving the following two theorems: (i) The graph GR is a Hamming graph if and only if R is strongly incompatible. (ii) The graph GR is a block graph with #R blocks if and only if R is strongly compatible.