The inverse inertia problem for graphs: Cut vertices, trees, and a counterexample |
| |
Authors: | Wayne Barrett H Tracy Hall Raphael Loewy |
| |
Institution: | a Department of Mathematics, Brigham Young University, Provo, UT 84602, United States b Department of Mathematics, Technion - Israel Institute of Technology, Haifa 32000, Israel |
| |
Abstract: | Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n×n matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The inverse inertia problem for G asks which inertias can be attained by a matrix in S(G). We give a complete answer to this question for trees in terms of a new family of graph parameters, the maximal disconnection numbers of a graph. We also give a formula for the inertia set of a graph with a cut vertex in terms of inertia sets of proper subgraphs. Finally, we give an example of a graph that is not inertia-balanced, which settles an open problem from the October 2006 AIM Workshop on Spectra of Families of Matrices described by Graphs, Digraphs and Sign Patterns. We also determine some restrictions on the inertia set of any graph. |
| |
Keywords: | 05C05 05C50 15A03 15A57 |
本文献已被 ScienceDirect 等数据库收录! |
|