Front for the arXiv
Fri, 9 May 2008
Front > math > CO > 0711 > arXiv:0711.3049
search | register | submit
journals | about | iFAQ

arXiv:0711.3049

[pdf] [ps] [dvi] [src] [arxiv]

Title: The inverse inertia problem for graphs
Authors: Wayne Barrett, H. Tracy Hall, Raphael Loewy
Categories: math.CO Combinatorics (math.SP Spectral Theory)
Comments: 83 pages, 15 figures
MSC: 05C05, 05C50 (Primary); 15A03, 15A57 (Secondary)

Abstract: Let G be an undirected graph on n vertices and let S(G) be the set of all real symmetric n x 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, and investigate restrictions on the inertia set of any graph.

Owner: H. Tracy Hall
Version 1: Tue, 20 Nov 2007 01:22:09 GMT

[help e-mail] - for questions or comments about the Front
arXiv contact page - for questions about downloading and submitting e-prints