Title

On the dimension of trees

Authors

Authors

R. C. Brigham; G. Chartrand; R. D. Dutton;P. Zhang

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

Discret. Math.

Keywords

isometric embeddings; infinity norm; trees; Mathematics

Abstract

We consider isometric embedding of trees into the infinite graph Z(m) whose vertices are the m-dimensional lattice points where two vertices a = (a(1), a(2),..., a(m)) and b = (b(1), b(2),..., b(m)) are adjacent if and only if vertical bar a(i) - b(i)vertical bar <= 1 for 1 <= i <= m. Linial, London, and Rabinovich have shown that this can be done with m <= 1.7095 log(2) t, where t is the number of leaves. In this note, we sketch a proof that [log(2) t] <= m <= [1.45 log(2) t] (c) 2005 Elsevier B.V. All rights reserved.

Journal Title

Discrete Mathematics

Volume

294

Issue/Number

3

Publication Date

1-1-2005

Document Type

Article

Language

English

First Page

279

Last Page

283

WOS Identifier

WOS:000229354500005

ISSN

0012-365X

Share

COinS