Concerning the relationship between realizations and tight spans of finite metrics

Koolen, Jack (author)

Lesser, Alice (author): Uppsala universitet,Matematiska institutionen,Centrum för bioinformatik

Moulton, Vincent (author)

(creator_code:org_t)

2007-12-12
2007
English.
In: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 38:3, s. 605-614

Related links:: https://link.springe...; show more...; https://urn.kb.se/re...; https://doi.org/10.1...; show less...

Abstract Subject headings

Given a metric d on a finite set X, a realization of d is a weighted graph $G=(V,E,w\colon \ E \to {\Bbb R}_{>0})$ with $X \subseteq V$ such that for all $x,y \in X$ the length of any shortest path in G between x and y equals d(x,y). In this paper we consider two special kinds of realizations, optimal realizations and hereditarily optimal realizations, and their relationship with the so-called tight span. In particular, we present an infinite family of metrics {dk}k≥1, and—using a new characterization for when the so-called underlying graph of a metric is an optimal realization that we also present—we prove that dk has (as a function of k) exponentially many optimal realizations with distinct degree sequences. We then show that this family of metrics provides counter-examples to a conjecture made by Dress in 1984 concerning the relationship between optimal realizations and the tight span, and a negative reply to a question posed by Althofer in 1988 on the relationship between optimal and hereditarily optimal realizations.

About the subject

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.