Isometric Embeddings of Finite Metric Trees into $({\mathbb{R}}^n,d_1)$ and $({\mathbb{R}}^n,d_{\infty })$

Abstract

We investigate isometric embeddings of finite metric trees into $({\mathbb{R}}^n,d_1)$ and $({\mathbb{R}}^n,d_{\infty })$. We prove that a finite metric tree can be isometrically embedded into $({\mathbb{R}}^n,d_1)$ if and only if the number of its leaves is at most $2n$. We show that a finite star tree with at most $2^n$ leaves can be isometrically embedded into $({\mathbb{R}}^n,d_{\infty })$ and a finite metric tree with more than $2^n$ leaves cannot be isometrically embedded into $({\mathbb{R}}^n,d_{\infty })$. We conjecture that an arbitrary finite metric tree with at most $2^n$ leaves can be isometrically embedded into $({\mathbb{R}}^n,d_{\infty })$.

9 pages, 5 figures