On the lower length of the closed-set lattice of a tree

✍ Scribed by K.M. Koh; K.S. Poh

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 395 KB
• Volume: 151
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(94)00090-6

✦ Synopsis

Let L(T) be the closed-set latice of a tree T. The lower length l, (L(T)) of L (T) is defined as

Call a set S of vertices in T a sparse set if d(x, y)/> 3 for any two distinct vertices x, y in S. The sparsity y(T) of T is defined as y(T) = max {Isl: s is a sparse set of T}.

We prove that, for any tree T of order n, I,(L(T)) = n + 1 -7(T) and deduce from this that l, (L (T)) >1 ~ n/2 ] + 1. All trees T of order n such that l, (L (T)) = [-n/2 ] + 1 are characterized.