On the inertia set of a signed graph with loops

Abstract

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,\dots ,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 symmetric $n\times n$ real matrices $A=[a_{i,j}]$ such that if $a_{i,j}<0$, then there must be an even edge connecting $i$ and $j$; if $a_{i,j}>0$, then there must be an odd edge connecting $i$ and $j$; and if $a_{i,j}=0$, then either there must be an odd edge and an 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 \emph{inertia set} of $(G,\Sigma )$ as the set of the partial inertias of all matrices $A\in S(G,\Sigma )$. In this paper, we present a formula that allows us to obtain the minimal elements of the inertia set of $(G,\Sigma )$ in case $(G,\Sigma )$ has a $1$-separation using the inertia sets of certain signed graphs associated to the $1$-separation.

14 pages, 1 figure