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^=$.
تحميل البحث