Skip to main content
deleted 31 characters in body
Source Link
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

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. I suspect that, as well as the W(2) graph also have no decomposition.

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. I suspect that the W(2) graph also have no decomposition.

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.

deleted 384 characters in body
Source Link
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

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 and the odd cycles.

  3. $a<c$. There are a vast number of graphs in this case. As every graphThe odd cycles fall in this case have at least 7 vertices, the graphs with 7 or 8 verticesand they have no decomposition. We can also find graphs by bounds on $a$ and $c$: TheI suspect that the W(2) graph has $a=5$ and $c=10$, so one part of the decomposition has $a=2$ and the other has $a=3$. Case checking proved it impossible. Graphs can also be found by considering the smallest graphs with $a<c$ in a subgraph-closed family, but I haven't succeeded in finding anyhave no decomposition.

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 and the odd cycles.

  3. $a<c$. There are a vast number of graphs in this case. As every graph in this case have at least 7 vertices, the graphs with 7 or 8 vertices have no decomposition. We can also find graphs by bounds on $a$ and $c$: The W(2) graph has $a=5$ and $c=10$, so one part of the decomposition has $a=2$ and the other has $a=3$. Case checking proved it impossible. Graphs can also be found by considering the smallest graphs with $a<c$ in a subgraph-closed family, but I haven't succeeded in finding any.

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. I suspect that the W(2) graph also have no decomposition.

Source Link
LeechLattice
  • 9.5k
  • 2
  • 23
  • 57

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 and the odd cycles.

  3. $a<c$. There are a vast number of graphs in this case. As every graph in this case have at least 7 vertices, the graphs with 7 or 8 vertices have no decomposition. We can also find graphs by bounds on $a$ and $c$: The W(2) graph has $a=5$ and $c=10$, so one part of the decomposition has $a=2$ and the other has $a=3$. Case checking proved it impossible. Graphs can also be found by considering the smallest graphs with $a<c$ in a subgraph-closed family, but I haven't succeeded in finding any.