This book provides an introduction to the inverse eigenvalue problem for graphs (IEP-$G$) and the related area of zero forcing, propagation, and throttling. The IEP-$G$ grew from the intersection of linear algebra and combinatorics and has given rise to both a rich set of deep problems in that area as well as a breadth of “ancillary” problems in related areas. The IEP-$G$ asks a fundamental mathematical question expressed in terms of linear algebra and graph theory, but the significance of such questions goes beyond these two areas, as particular instances of the IEP-$G$ also appear as major research problems in other fields of mathematics, sciences and engineering. One approach to the IEP-$G$ is through rank minimization, a relevant problem in itself and with a large number of applications. During the past 10 years, important developments on the rank minimization problem, particularly in relation to zero forcing, have led to significant advances in the IEP-$G$. The monograph serves as an entry point and valuable resource that will stimulate future developments in this active and mathematically diverse research area.
Author(s): Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader
Series: Mathematical Surveys and Monographs, 270
Publisher: American Mathematical Society
Year: 2022
Language: English
Pages: 301
City: Providence
Front Cover
Contents
Preface
Part 1 Introduction to the Inverse Eigenvalue Problem of a Graph and Zero Forcing
CHAPTER 1: Introduction to and Motivation for the IEP-G
1.1. Forward Problems
1.2. Inverse Problems
1.3. Matrices, Forward Problems, and Structure
1.4. Inverse Eigenvalue Problems and Matrices with a Given Graph
1.5. Initial Results for the IEP-G
1.6. Connections of the IEP-G to Nodal Domains
CHAPTER 2: Zero Forcing and Maximum Eigenvalue Multiplicity
2.1. Introduction to Maximum Nullity and Minimum Rank
2.2. Introduction to Zero Forcing
2.3. Historical Background to the Minimum Rank Problem
2.4. Further Properties of Minimum Rank
2.5. Minimum Positive Semidefinite Rank and Zero Forcing Number
2.6. Colin de Verdiere Type Parameters
2.7. The δ-Conjecture and the Graph Complement Conjecture
Part 2 Strong Properties, Theory, and Consequences
CHAPTER 3: Implicit Function Theorem and Strong Properties
3.1. Implicit Function Theorem
3.2. Strong Properties
3.3. Strong Properties for Sign Patterns
CHAPTER 4: Consequences of the Strong Properties
4.1. Number of Distinct Eigenvalues
4.2. Augmentation Lemma
4.3. The IEP-G for Small Graphs
4.4. Verification Matrices
4.5. Matrix Liberation Lemma
4.6. Minor Monotonicity
4.7. Guaranteed Strong Properties
CHAPTER 5: Theoretical Underpinnings of the Strong Properties
5.1. Spaces of Matrices
5.2. Manifolds and Tangent Spaces
5.3. Implicit Function Theorem Revisited
5.4. Strong Properties and Supergraph Lemma Revisited
5.5. Bifurcation Lemma
5.6. Tangent Space Matrix
5.7. Matrix Liberation Lemma Revisited
5.8. Future Work
Part 3 Further Discussion of Ancillary Problems
CHAPTER 6: Ordered Multiplicity Lists of a Graph
6.1. Multiplicity Lists for Special Families of Graphs
6.2. Constructive Techniques
6.3. Related Graph Parameters
6.4. Path Removal and Multiplicities for Trees
CHAPTER 7: Rigid Linkages
7.1. Rigid Linkages
7.2. Rigid Shortest Linkages
CHAPTER 8: Minimum Number of Distinct Eigenvalues
8.1. Number of Distinct Eigenvalues for Adjacency Matrices
8.2. Basic Results
8.3. Strong Properties and q
8.4. Joins and Graphs with Small q
8.5. A Nordhaus-Gaddum Conjecture for q
8.6. Minimum Number of Distinct Eigenvalues for Trees
Part 4 Zero Forcing, Propagation Time, and Throttling
CHAPTER 9: Zero Forcing, Variants, and Related Parameters
9.1. Standard Zero Forcing, Z(G)
9.2. Universal Definitions for Zero Forcing
9.3. Positive Semidefinite Zero Forcing, Z+(G)
9.4. Skew Forcing, Z_(G)
9.5. Connected and Total Zero Forcing
9.6. Additional Zero Forcing Parameters Related to the IEP-G
9.7. Rigid Linkage Zero Forcing
9.8. Minor Monotone Floors of Zero Forcing Parameters
9.9. Power Domination, γP (G)
9.10. Cops and Robbers, c(G)
9.11. Average Values and Random Graphs
9.12. Topics Not Covered
CHAPTER 10: Propagation Time and Capture Time
10.1. Universal Definitions for Forcing Propagation Time
10.2. Z-Propagation Time
10.3. Z+-Propagation Time
10.4. Z_-Propagation Time
10.5. Propagation Time for Power Domination
10.6. Capture Time for Cops and Robbers
10.7. Expected Propagation Time for Probabilistic Zero Forcing
10.8. Topics Not Covered
CHAPTER 11: Throttling
11.1. Universal Definitions for Forcing Throttling
11.2. Z-throttling
11.3. Z+-throttling
11.4. Z_-throttling
11.5. Throttling for Power Domination
11.6. Throttling for Cops and Robbers
11.7. Product Throttling
11.8. Topics Not Covered
APPENDIX A Graph Terminology and Notation
Bibliography
Index
Back Cover
