Given an undirected connected graph on $n$ nodes, let $S$ be the subspace of vectors $x \in \mathbb{R}^n$ which satisfy $$\sum_{j \in N(i)} x_j = 0,$$ for all $i=1, \ldots, n$. Here $N(i)$ is the set of neighbors of node $i$; the graph may have self-loops so that it is possible that $i \in N(i)$. I am interested in understanding the dimension of $S$.

Some examples:

  • On the complete graph with self-loops at every node, ${\rm dim}(S)=n-1$.
  • On the ring with four nodes, ${\rm dim}(S)=2$.
  • On the line with three nodes and self-loops at every node, ${\rm dim}(S)=0$.

My question: can any connections between ${\rm dim}(S)$ and any combinatorial graph quantities be made?


Note that what you defined is simply the dimension of the nullspace of the adjacency matrix of $G$. This is usually called the nullity $\eta(G)$ of $G$. Apparently, this parameter is significant in Chemistry. If $\eta(G)>0$ for a molecular graph, then the corresponding compound is highly reactive. See this survey for more information.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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