A typical vertex of a tree

Abstract

Let T denote a tree with at least three vertices. Observe that T contains a vertex which has at least two neighbors of degree one or two. A class of algorithms on trees related to the observation are discussed and characterized. One of the example is an algorithm to compute the minimum rank m(T) of the symmetric matrices with prescribed graph T, which is easier to process than the algorithm previous found by Nylen [Linear Algebra Appl. 248 (1996) 303-316]. Two interpretations of the number m(T) in terms of some combinatorial properties on trees are given. (C) 2001 Elsevier Science B.V. All rights reserved. MSC: 05C05.