Book contents
- Frontmatter
- Dedication
- Contents
- Preface
- List of Terms and Symbols
- 0 Background
- 1 Introduction
- 2 Parter-Wiener, etc. Theory
- 3 Maximum Multiplicity for Trees, I
- 4 Multiple Eigenvalues and Structure
- 5 Maximum Multiplicity, II
- 6 The Minimum Number of Distinct Eigenvalues
- 7 Construction Techniques
- 8 Multiplicity Lists for Generalized Stars
- 9 Double Generalized Stars
- 10 Linear Trees
- 11 Nontrees
- 12 Geometric Multiplicities for General Matrices over a Field
- Appendix A Multiplicity Lists for Trees on Fewer Than 12 Vertices
- Appendix B Seeds for Branch Duplication
- Bibliography
- Index
11 - Nontrees
Published online by Cambridge University Press: 09 February 2018
- Frontmatter
- Dedication
- Contents
- Preface
- List of Terms and Symbols
- 0 Background
- 1 Introduction
- 2 Parter-Wiener, etc. Theory
- 3 Maximum Multiplicity for Trees, I
- 4 Multiple Eigenvalues and Structure
- 5 Maximum Multiplicity, II
- 6 The Minimum Number of Distinct Eigenvalues
- 7 Construction Techniques
- 8 Multiplicity Lists for Generalized Stars
- 9 Double Generalized Stars
- 10 Linear Trees
- 11 Nontrees
- 12 Geometric Multiplicities for General Matrices over a Field
- Appendix A Multiplicity Lists for Trees on Fewer Than 12 Vertices
- Appendix B Seeds for Branch Duplication
- Bibliography
- Index
Summary
Introduction and Observations
The problem of multiplicity lists for Hermitian matrices is remarkably different when the underlying graph G is not a tree. Some highly algebraic aspects of the problem are the same. For example,
• Maximum multiplicity in H(G) corresponds to minimum rank in H(G).
• Multiplicity can change by at most 1 when a vertex is removed.
• Multiplicity can change under perturbation by at most the rank of the perturbation.
• Many of the results on perturbation of diagonal entries (Section 4.1) are the same.
However, as seen in Chapter 2, there is little vestige of the technology of Parter vertices for general graphs, and it maywell be that all vertices are downers, even when multiple eigenvalues are present. Two of the construction techniques we have described in Chapter 7 are almost not available, and the third, the IFT, is more problematic to carry out. The similarities above are too weak to be very helpful, and minimum rank for general graphs is known to be very subtle, while it has a lovely answer for trees. Thus, determination of possible multiplicities is even more difficult for general graphs and often involves looking at very particular cases.
There are some things that have been said, or can be said, and we review a selection of them here.
The Complete Graph
The complete graph Kn on n ≥ 2 vertices is relatively easy to analyze, as it allows many multiplicity lists. However, it requires different techniques to verify that various spectra occur, and these techniques are useful for other dense graphs that we pursue in Section 11.7. One list that Kn obviously does not allow is just one eigenvalue of multiplicity n. An Hermitian matrix with this list would be similar to, and thus, equal to, a multiple of I. It would be diagonal and thus is allowed only by the trivial graph with n vertices and no edges.
- Type
- Chapter
- Information
- Eigenvalues, Multiplicities and Graphs , pp. 211 - 231Publisher: Cambridge University PressPrint publication year: 2018