Diameter minimal trees

Charles Denise Johnson, Carlos M. Saiago

Research output: Contribution to journalArticle

6 Citations (Scopus)

Abstract

Using the method of seeds and branch duplication, it is shown that for every tree of diameter d <7, there is an Hermitian matrix with as few as d distinct eigenvalues (a known lower bound). For diameter 7, some trees require 8 distinct eigenvalues, but no more; the seeds for which 7 and 8 are the worst case are classified. For trees of diameter d, it is shown that, in general, the minimum number of distinct eigenvalues is bounded by a function of d. Many trees of high diameter permit as few of distinct eigenvalues as the diameter and a conjecture is made that all linear trees are of this type. Several other specific, related observations are made.

Original languageEnglish
Pages (from-to)557-571
Number of pages15
JournalLinear & Multilinear Algebra
Volume64
Issue number3
DOIs
Publication statusPublished - 3 Mar 2016

Keywords

  • branch duplication
  • diameter
  • distinct eigenvalues
  • Hermitian matrix
  • multiplicities
  • tree
  • SYMMETRIC-MATRICES
  • EIGENVALUES
  • GRAPH

Cite this