The inertia set of a signed graph

A signed graph is a pair (G, Sigma), where G = (V, E) is a graph (in which parallel edges are permitted, but loops are not) with V = {1, ..., n} and Sigma subset of E. The edges in Sigma are called odd edges and the other edges of E even. By S(G, Sigma) we denote the set of all symmetric V x V matrices A = [a(i,j)] with a(i,j) < 0 if i and j are adjacent and all edges between i and j are even, a(i,j) > 0 if i and j are adjacent and all edges between i and j are odd, a(i,j) is an element of R if i and j are connected by even and odd edges, a(i,j) = 0 if i not equal j and i and j are non-adjacent, and a(i,j) is an element of R for all vertices i. The stable inertia set of a signed graph (G, Sigma) is the set of all pairs (p, q) for which there exists a matrix A is an element of S(G, Sigma) with p positive and q negative eigenvalues which has the Strong Arnold Property. In this paper, we study the stable inertia set of (signed) graphs. (C) 2013 Elsevier Inc. All rights reserved.