ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Generalizations of the Strong Arnold Property and the Inverse Eigenvalue Problem of a Graph

Tue 11:30–12:00, Room AV 04.17
Two-connected signed graphs with maximum nullity at most two
Marina Arav (Georgia State University)
Joint work with Frank J. Hall; Hein van der Holst; Zongshan Li

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 $\Sigma\subseteq 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 $n\times 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\not=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 $A\in S(G,\Sigma)$ and the largest nullity of any matrix $A\in S(G,\Sigma)$ that has the Strong Arnold Property, respectively. In this talk, we discuss the characterizations of the classes of signed graphs $(G,\Sigma)$ with $M(G,\Sigma)\leq 1$, of the class of signed graphs $(G,\Sigma)$ with $\xi(G,\Sigma)\leq 1$, of the class of $2$-connected signed graphs $(G,\Sigma)$ with $M(G,\Sigma)\leq 2$, and of the class of $2$-connected signed graphs $(G,\Sigma)$ with $\xi(G,\Sigma)\leq 2$.