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?



Vectors which average to zero over any graph neighborhood
Note that what you defined is simply the dimension of the nullspace of the [adjacency matrix](https://www.wikiwand.com/en/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](http://elib.mi.sanu.ac.rs/files/journals/zr/22/zbr14137.pdf) for more information. 


