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?

  • 1
    $\begingroup$ $d$ is meant to be $b$? (or, vice versa?) $\endgroup$ – Gerry Myerson Jul 9 '18 at 1:10
  • $\begingroup$ Dear Daniel, I made some small corrections, the least small of which was to make it explicit that 'disjoint' means 'vertex-disjoint'. The latter tends to be the most usual interpretation of 'disjoint subgraphs'. I am not entirely sure you meant it that way, though; of course you can re-correct it if necessary. $\endgroup$ – Peter Heinig Jul 22 '18 at 12:12

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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.