On the dimension of trees

    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