×

Diameter minimal trees. (English) Zbl 1338.05160

For a tree \(T\) with \(n\) vertices, let \(S(T)\) denote all the \(n \times n\) Hermitian matrices whose off-diagonal elements are non zero iff the entries of the adjacency matrix of \(T\) is non zero. Using the method of seeds and branch duplication, it is shown that for every tree of diameter \(d<7\), there is an Hermitian matrix in \(S(T)\) 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.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C12 Distance in graphs
05C35 Extremal problems in graph theory
05C05 Trees
15A18 Eigenvalues, singular values, and eigenvectors
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1137/S0895479801393320 · Zbl 1067.15003 · doi:10.1137/S0895479801393320
[2] DOI: 10.1080/03081089908818608 · Zbl 0929.15005 · doi:10.1080/03081089908818608
[3] Leal-Duarte A, Math. Inequal. Appl 5 pp 175– (2002)
[4] DOI: 10.1080/03081080600597668 · Zbl 1149.15007 · doi:10.1080/03081080600597668
[5] DOI: 10.1002/nla.332 · Zbl 1164.93340 · doi:10.1002/nla.332
[6] DOI: 10.1016/S0024-3795(03)00582-2 · Zbl 1035.15010 · doi:10.1016/S0024-3795(03)00582-2
[7] DOI: 10.1016/0024-3795(89)90295-4 · Zbl 0661.15024 · doi:10.1016/0024-3795(89)90295-4
[8] DOI: 10.1016/j.laa.2008.04.016 · Zbl 1143.15005 · doi:10.1016/j.laa.2008.04.016
[9] DOI: 10.1007/s10801-008-0121-8 · Zbl 1226.05158 · doi:10.1007/s10801-008-0121-8
[10] DOI: 10.1016/j.disc.2014.04.030 · Zbl 1298.05068 · doi:10.1016/j.disc.2014.04.030
[11] Horn R, Matrix analysis, 2. ed. (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.