Inertial decomposition of graphs

Question

The problem is this: given a graph $G$, to find a decomposition of $G$, i.e. a set $F$ of vertex-disjoint proper subgraphs of $G$ such that:

$$\text{inertia}(G) = \sum_{H \in F} \operatorname{inertia}(H)$$

where $\operatorname{inertia}(G)=(a,b,c)$, with $a$ equals the number of negative eigenvalues of $A(G)$, the adjacency matrix of $G$, $b$ equals the dimension of null space of $A(G)$, and $c$ equals the number of positive eigenvalues of $A(G)$. I cannot find any paper about this problem. Does anyone know something about this problem?

Answer 1

There is a decomposition when $b≠0$: Let $v$ be a nonzero vector in the null space of $A(G)$, and let $n$ be a vertex where $V_n≠0$. Then we can decompose the graph into two parts: $n$ and $G\backslash n$.

The statement $\text{inertia}(G) = \text{inertia}(n)+\text{inertia}(G\backslash n)$ is equivalent to the statement that $A(G)$ and $SA(G)S$ have the same inertia, where S is a diagonal matrix with $S_{ii}=1$ for $i≠n$ and $S_{nn}=0$.

Since $V_n≠0$, $A(G)$ and $SA(G)S$ have the same rank. It suffices to prove $A(G)$ and $SA(G)S$ have the same number of positive eigenvalues.

Consider a mapping: $f:t\rightarrow SA(G)S$ where S is a diagonal matrix with $S_{ii}=1$ for $i≠n$ and $S_{nn}=t$, $t\in [0,1]$. Since the change of eigenvalues is continuous, if some eigenvalue changed sign between $t=0$ and $t=1$, there must be a $t$ where the eigenvalue equals $0$, which is a contradiction to Sylvester's law of inertia. So the eigenvalues never change sign, it follows that $A(G)$ and $SA(G)S$ have the same inertia. Thus the decomposition $G=n\cup G\backslash n$ is valid.

If $b=0$, there are three cases:

1. $a=c$. It seems that such graphs have a perfect matching, so a decomposition into disjoint edges would suffice.

2. $a>c$. It seems that the only graphs in this case without any decomposition are the complete graphs.

3. $a<c$. The odd cycles fall in this case, and they have no decomposition, as well as the W(2) graph.