Two-connected signed graphs with maximum nullity at most two

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

paper · doi:10.48550/arxiv.1407.2525

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. 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 adjacent and connected by only even edges, a_i,j>0 if i and j are adjacent and 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 parameters M(G,Σ) and ξ(G,Σ) of a signed graph (G,Σ) are the largest nullity of any matrix A∈ S(G,Σ) and the largest nullity of any matrix A∈ S(G,Σ) that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs (G,Σ) with M(G,Σ)≤ 1 and of signed graphs with ξ(G,Σ)≤ 1. In this paper, we characterize the 2-connected signed graphs (G,Σ) with M(G,Σ)≤ 2 and the 2-connected signed graphs (G,Σ) with ξ(G,Σ)≤ 2.

Related

• A graph minors characterization of signed graphs whose signed Colin de Verdière parameter ν is two
• No signed graph with the nullity η(G,σ)=|V(G)|-2m(G)+2c(G)-1
• An upper bound on the nullity of signed graphs
• The inertia set of a signed graph
• Further results on the nullity of signed graphs