A typical vertex of a tree

Ping Hong Wei, Chih-wen Weng*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish
Pages (from-to)337-345
Number of pages9
JournalDiscrete Mathematics
Volume226
Issue number1-3
DOIs
StatePublished - 1 Jan 2001

Keywords

  • Rank

Fingerprint Dive into the research topics of 'A typical vertex of a tree'. Together they form a unique fingerprint.

Cite this