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:00–11:30, Room AV 04.17
On the Northeast Property of Signed Graphs with Loops
Hein van der Holst (Georgia State University)
Joint work with Marina Arav (Georgia State University); John Sinkovic (University of Waterloo)

A signed graph is a pair $(G,\Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges and loops are permitted) with $V=\{1,\ldots,n\}$ and $\Sigma\subseteq E$. The edges in $\Sigma$ are called odd edges and the other edges of $E$ even. By $S(G,\Sigma)$ we denote the set of all $n\times n$ symmetric real matrices $A=[a_{i,j}]$ such that if $a_{i,j} < 0$, then among the edges connecting $i$ and $j$, there must be at least one even edge; if $a_{i,j} > 0$, then among the edges connecting $i$ and $j$, there must be at least one odd edge; and if $a_{i,j} = 0$, then either there must be at least one odd edge and at least one even edge connecting $i$ and $j$, or there are no edges connecting $i$ and $j$. (Here we allow $i=j$.) For a symmetric real matrix $A$, the partial inertia of $A$ is the pair $(p,q)$, where $p$ and $q$ are the number of positive and negative eigenvalues of $A$, respectively. If $(G,\Sigma)$ is a signed graph, we define the inertia set of $(G,\Sigma)$ as the set of the partial inertias of all matrices $A \in S(G,\Sigma)$. By $\mbox{MR}(G,\Sigma)$ we denote $\max\{\mbox{rank}(A) \mid A\in S(G,\Sigma)\}$. We say that a signed graph $(G,\Sigma)$ satisfies the Northeast Property if for each $(p,q)$ with $p+q<\mbox{MR}(G,\Sigma)$ in the inertia set of $(G,\Sigma)$, also $(p+1,q), (p,q+1)$ belong to the inertia set of $(G,\Sigma)$.

In the talk, we show that if $(G,\Sigma)$ is a signed graph, where $G$ a tree with possibly loops attached at some of the vertices, then $(G,\Sigma)$ satisfies the Northeast Property. We also show that a weaker form of the Northeast Property holds for all signed graphs. Furthermore, we present a formula for calculating the inertia set of a signed graph $(G,\Sigma)$, where $G$ is a tree with possibly loops attached at some of the vertices.