System disruptions
There are recurring service disruptions on some of the search portals due to high traffic. We are working to resolve the issue, you may temporarily encounter an error message.
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Injective Split Systems
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
Show others and affiliations
Number of Authors: 52023 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 39, no 4, article id 65Article in journal (Refereed) Published
Abstract [en]

A split system S on a finite set X, |X|≥3, is a set of bipartitions or splits of X which contains all splits of the form {x,X−{x}}, x∈X. To any such split system S we can associate the Buneman graph B(S) which is essentially a median graph with leaf-set X that displays the splits in S. In this paper, we consider properties of injective split systems, that is, split systems S with the property that medB(S)(Y)≠medB(S)(Y′) for any 3-subsets Y,Y′ in X, where medB(S)(Y)med denotes the median in B(S) of the three elements in Y considered as leaves in B(S). In particular, we show that for any set X there always exists an injective split system on X, and we also give a characterization for when a split system is injective. We also consider how complex the Buneman graph B(S) needs to become in order for a split system S on X to be injective. We do this by introducing a quantity for |X| which we call the injective dimension for |X|, as well as two related quantities, called the injective 2-split and the rooted-injective dimension. We derive some upper and lower bounds for all three of these dimensions and also prove that some of these bounds are tight. An underlying motivation for studying injective split systems is that they can be used to obtain a natural generalization of symbolic tree maps. An important consequence of our results is that any three-way symbolic map on X can be represented using Buneman graphs.

Place, publisher, year, edition, pages
2023. Vol. 39, no 4, article id 65
Keywords [en]
Median graph, Split system, Buneman graph
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:su:diva-220558DOI: 10.1007/s00373-023-02660-wISI: 001002775300001Scopus ID: 2-s2.0-85154028305OAI: oai:DiVA.org:su-220558DiVA, id: diva2:1793982
Available from: 2023-09-04 Created: 2023-09-04 Last updated: 2023-09-04Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hellmuth, Marc

Search in DiVA

By author/editor
Hellmuth, Marc
By organisation
Department of Mathematics
In the same journal
Graphs and Combinatorics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 85 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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