Yet another graph invariant: the similarity matrix

This is nice. What is the motivation for dividing by $\epsilon(u)+\epsilon(v)$?

To partly answer your first question, I suspect the notion of $n$-neighborhood is relatively common, but one place where it is very common, if not a staple, in Finite Model Theory (read also Database Theory). It is a key component of various locality properties, notably Gaifman locality. The quantity $s(u,v)$ is closely related to the complexity of distinguishing $u$ from $v$ by a first-order query in the language of graphs. Specifically, a query of quantifier depth $k$ cannot distinguish between vertices such that $s(u,v) > (3^{k+1}-1)/2$. This has many uses, a typical example is to measure the complexity of distinguishing database entries. A good intro can be found in the first few chapters of Libkin's Elements of Finite Model Theory.


This is an interesting question! Just a couple of (hopefully) pertinent things that come to mind...

  1. When you refer to "matrix equivalence" you essentially mean the ordering of the vertices, is that right? This would correspond to a permutation similarity of the matrix (ordinary matrix similarity, with respect to a permutation matrix) but this is almost always left unsaid in graph theory anyhow. (We often refer to "the" adjacency matrix of a graph, for instance.)

  2. Certainly two graphs with the same similarity matrix need not be isomorphic, as any two vertex transitive graphs will each have a similarity matrix of all 1's.