An explicit upper bound on disparity for trees of a given diameter

ABSTRACT

It is known that the minimum number of distinct eigenvalues c(T) of a symmetric matrix whose graph is a given tree T is at least the diameter d(T) of that tree. However, the disparity c(T) − d(T) can be positive. Using branch duplication and rooted seeds, the notion of the ‘most complex seed’ is introduced, and an explicit upper bound on the disparity is given for any tree of a given diameter.

Keywords:

• Branch duplication
• distinct eigenvalues
• graph of a matrix
• seed
• rooted seed

AMS Classifications:

• 15A18
• 05B20
• 05C50

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by the National Science Foundation [Grant DMS #0751964].