Signed graphs with maximum nullity two

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. The edges in Σ are called odd and the other edges of E even. If there are parallel edges, then only two edges in each parallel class are permitted, one of which is even and one of which is odd. By S(G,Σ) we denote the set of all symmetric n×n matrices A=[a_i,j] with a_i,j<0 if i and j are connected by an even edge, a_i,j>0 if i and j are connected by an odd edge, a_i,j∈R if i and j are connected by both an even and an odd edge, a_i,j=0 if i≠j and i and j are non-adjacent, and a_i,i∈R for all vertices i. The maximum nullity M(G,Σ) of a signed graph (G,Σ) is the maximum nullity attained by any A∈S(G,Σ). Arav et al. gave a combinatorial characterization of 2-connected signed graphs (G,Σ) with M(G,Σ)=2. In this paper, we give a complete combinatorial characterization of the signed graphs (G,Σ) with M(G,Σ)=2.