1
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .