Replacing cliques by stars in quasi-median graphs (2004)
AuthorsHuber, K.T., Moulton, V., Semple, C.show all
For a multi-set Σ of splits (bipartitions) of a finite set X, we introduce the multi-split graph G(Σ). This graph is a natural extension of the Buneman graph. Indeed, it is shown that several results pertaining to the Buneman graph extend to the multi-split graph. In addition, in case Σ is derived from a set R of partitions of X by taking parts together with their complements, we show that the extremal instances where R is either strongly compatible or strongly incompatible are equivalent to G(Σ) being either a tree or a Cartesian product of star trees, respectively.
CitationHuber, K.T., Moulton, V., Semple, C. (2004) Replacing cliques by stars in quasi-median graphs. Discrete Applied Mathematics, 143(1-3), pp. 194-203.
This citation is automatically generated and may be unreliable. Use as a guide only.