Sökning: onr:"swepub:oai:DiVA.org:uu-96396" >
Concerning the rela...
Concerning the relationship between realizations and tight spans of finite metrics
-
Koolen, Jack (författare)
-
- Lesser, Alice (författare)
- Uppsala universitet,Matematiska institutionen,Centrum för bioinformatik
-
Moulton, Vincent (författare)
-
(creator_code:org_t)
- 2007-12-12
- 2007
- Engelska.
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 38:3, s. 605-614
- Relaterad länk:
-
https://link.springe...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics (hsv//eng)
Nyckelord
- MATHEMATICS
- MATEMATIK
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
Hitta via bibliotek
Till lärosätets databas