Two-connected signed graphs with maximum nullity at most two

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,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma)$ we denote the set of all symmetric $ntimes 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}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameters $M(G,Sigma)$ and $xi(G,Sigma)$ of a signed graph $(G,Sigma)$ are the largest nullity of any matrix $Ain S(G,Sigma)$ and the largest nullity of any matrix $Ain S(G,Sigma)$ that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 1$ and of signed graphs with $xi(G,Sigma)leq 1$. In this paper, we characterize the $2$-connected signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 2$ and the $2$-connected signed graphs $(G,Sigma)$ with $xi(G,Sigma)leq 2$.

Minimum ranks of sign patterns via sign vectors and duality

A {it sign pattern matrix} is a matrix whose entries are from the set ${+,-, 0}$. The minimum rank of a sign pattern matrix $A$ is the minimum of the ranks of the real matrices whose entries have signs equal to the corresponding entries of $A$. It is shown in this paper that for any $m times n$ sign pattern $A$ with minimum rank $n-2$, rational realization of the minimum rank is possible. This is done using a new approach involving sign vectors and duality. It is shown that for each integer $ngeq 9$, there exists a nonnegative integer $m$ such that there exists an $ntimes m$ sign pattern matrix with minimum rank $n-3$ for which rational realization is not possible. A characterization of $mtimes n$ sign patterns $A$ with minimum rank $n-1$ is given (which solves an open problem in Brualdi et al. cite{Bru10}), along with a more general description of sign patterns with minimum rank $r$, in terms of sign vectors of certain subspaces. A number of results on the maximum and minimum numbers of sign vectors of $k$-dimensional subspaces of $mathbb R^n$ are obtained. In particular, it is shown that the maximum number of sign vectors of $2$-dimensional subspaces of $mathbb R^n$ is $4n+1$. Several related open problems are stated along the way.

The minimum rank of a sign pattern matrix with a 1-separation

A sign pattern matrix is a matrix whose entries are from the set ${+,-,0}$. If $A$ is an $mtimes n$ sign pattern matrix, the qualitative class of $A$, denoted $Q(A)$, is the set of all real $mtimes n$ matrices $B=[b_{i,j}]$ with $b_{i,j}$ positive (respectively, negative, zero) if $a_{i,j}$ is + (respectively, $-$, 0). The minimum rank of a sign pattern matrix $A$, denoted $mr(A)$, is the minimum of the ranks of the real matrices in $Q(A)$. Determination of the minimum rank of a sign pattern matrix is a longstanding open problem. For the case that the sign pattern matrix has a 1-separation, we present a formula to compute the minimum rank of a sign pattern matrix using the minimum ranks of certain generalized sign pattern matrices associated with the 1-separation.

A graph minors characterization of signed graphs whose signed Colin de Verdi`ere parameter $ u$ is two

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 $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges even. By $S(G,Sigma)$ we denote the set of all symmetric $ntimes n$ 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}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameter $ u(G,Sigma)$ of a signed graph $(G,Sigma)$ is the largest nullity of any positive semidefinite matrix $Ain S(G,Sigma)$ that has the Strong Arnold Property. By $K_3^=$ we denote the signed graph obtained from $(K_3,emptyset)$ by adding to each even edge an odd edge in parallel. In this paper, we prove that a signed graph $(G,Sigma)$ has $ u(G,Sigma)leq 2$ if and only if $(G,Sigma)$ has no minor isomorphic to $(K_4,E(K_4))$ or $K_3^=$.

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 $Sigmasubseteq E$. By $S(G,Sigma)$ we denote the set of all symmetric $Vtimes 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}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{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 $Ain 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.