The inertia set of a signed graph

2012/08/27 by Arav, Marina, Hall, Frank J., Li, Zhongshan +1
#05C05 #05C22 #05C50 #05C83 #15A03 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1208.5285

Abstract

A signed graph is a pair (G,Σ), where G=(V,E) is a graph (in which parallel edges are permitted, but loops are not) with V=1,...,n and Σ⊆ E. By S(G,Σ) we denote the set of all symmetric V× V matrices A=[a_i,j] with a_i,j<0 if i and j are connected by only even edges, a_i,j>0 if i and j are connected by only odd edges, a_i,j∈ ℝ if i and j are connected by both even and odd edges, a_i,j=0 if i\not=j and i and j are non-adjacent, and a_i,i ∈ ℝ for all vertices i. The stable inertia set of a signed graph (G,Σ) is the set of all pairs (p,q) for which there exists a matrix A∈ S(G,Σ) 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.

Related

• On the inertia set of a signed graph with loops
• Inertias of Laplacian matrices of weighted signed graphs
• Characterizing the positive inertia index of connected signed graphs in terms of girth
• Connected signed graphs with given inertia indices and given girth
• Inertia Sets For Families of Graphs