Inertia sets for graphs on six or fewer vertices

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), a question which was previously answered when G is a tree. In this paper, a number of new techniques are developed in order to be able to determine possible inertias of general graphs: covers with cliques, covers with cliques and clique-stars, and the graph operations of edge subdivision, edge deletion, joins, and unions. Because most of the associated theorems require additional hypotheses, definitive criteria that apply to all graphs cannot be provided. Nevertheless, these results are strong enough to be able to determine the inertia set of each graph on 6 or fewer vertices and can be applied to many graphs with larger order as well. One consequence of the 1–6 vertex results is the fact that all of these graphs have balanced inertia. It is also mentioned which of these results guarantee or preserve balanced inertia, and explain how to modify them to include Hermitian matrices.