uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Replacing cliques by stars in quasi-median graphs
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, The Linnaeus Centre for Bioinformatics.
Uppsala University, Teknisk-naturvetenskapliga vetenskapsområdet, Faculty of Science and Technology, Biology, The Linnaeus Centre for Bioinformatics.
2004 (English)In: Discrete Applied Mathematics, Vol. 143, no 1-3, 194-203 p.Article in journal (Refereed) Published
Abstract [en]

For a multi-set Sigma of splits (bipartitions) of a finite set X, we introduce the multi-split graph G(Sigma). 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 Sigma 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(Sigma) being either a tree or a Cartesian product of star trees, respectively.

Place, publisher, year, edition, pages
2004. Vol. 143, no 1-3, 194-203 p.
Keyword [en]
split, (in)compatibility, strong (in)compatibility. buneman graph, multi-split graph, quasi-median graph, networks, trees
Identifiers
URN: urn:nbn:se:uu:diva-71813OAI: oai:DiVA.org:uu-71813DiVA: diva2:99724
Available from: 2005-05-12 Created: 2005-05-12 Last updated: 2011-01-12

Open Access in DiVA

No full text

By organisation
The Linnaeus Centre for Bioinformatics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 268 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf