Yet another graph invariant: the similarity matrix

Preliminaries

Let $n \in \mathbb{N}$ and $v$ be a vertex of a graph $G$. Let the $n$-neighbourhood of $v$, $N_n(v)$, be the induced subgraph of $G$ containing $v$ and all vertices at most $n$ edges away from $v$.

With $\epsilon(v)$ the eccentricity of $v$, $N_{\epsilon(v)}(v)$ is obviously nothing but the connected component of $G$ containing $v$, so it is natural to restrict $n$ for a given $v$ to the values $0,1, ..., \epsilon(v)$.

Consider for any two vertices $v$, $w$ the greatest $s = s(v,w)$ such that $N_s(v)$ and $N_s(w)$ are isomorphic [added:] with the isomorphism sending $v$ to $w$ (for short: $N_s(v) \cong_{vw} N_s(w)$). If $s(v,w) = \epsilon(v) = \epsilon(w)$, $v$ and $w$ are conjugate. For non-conjugate vertices $v$, $w$ the number $s= s(v,w)$ reflects the size of the smallest neighbourhood that is needed to distinguish $v$ and $w$, since $N_{s+1}(v) \ncong_{vw} N_{s+1}(w)$ by definition.

Let's call the positive number

$$\sigma(v,w) = \frac{2 \cdot s(v,w)}{\epsilon(v) + \epsilon(w)}$$

the similarity index of $v$ and $w$.

$\sigma(v,w) = 0$ indicates that $v$, $w$ have different $1$-neighbourhoods (and are maximally dissimilar), $\sigma(v,w) = 1$ indicates that $v$, $w$ are conjugate (i.e. maximally similar = indistinguishable by their neighbourhoods).

The matrix $\Sigma(G) = \lbrace \sigma(v,w) \rbrace_{v,w \in V(G)}$ reflects the symmetry of the graph $G$:

• If $\sigma(v,w) = 1$ only if $v = w$, the graph is asymmetric.
• If the $1$'s of the matrix come in square blocks along the diagonal, these blocks indicate the orbits of the graph.

$\Sigma(G)$ is a graph invariant up to matrix equivalence. (Is this the right wording?)

Definition: An $n \times n$-matrix $S$ is a similarity matrix iff there is a graph $G$ such that $S = \Sigma(G)$.

Questions

Is the notion of $n$-neighbourhood treated in other contexts, maybe under another name?

Is there already research on this concept of similarity (or a related one)?

How might similarity matrices be characterized (sufficient/necessary conditions)? ("A matrix is a similarity matrix if ...") Any idea?

How will graphs with the same similarity matrix (plus same eccentricity vector) be related? (They will probably not be don't have to be isomorphic, but maybe something weaker?)

-
Wouldn't you want the isomorphism between N_s(v) and N_s(w) to send v to w? – Qiaochu Yuan Jan 12 '10 at 13:03
Good question! I guess I should have wanted this, but I am not quite sure. (Maybe it's not necessary?) – Hans Stricker Jan 12 '10 at 13:12

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.

-
The motivation for dividing by $\epsilon(v) + \epsilon(w)$ was to get $\sigma(v,w) = 1$ iff $v$ and $w$ are conjugate. The information lost by this division can be added again by explicitely giving the eccentricity vector. – Hans Stricker Jan 13 '10 at 7:17
Your hint to Gaifman was great! This really gives me a kick. – Hans Stricker Jan 13 '10 at 8:02

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.

-
ad 1.: Yes, this is right. How would you have said it? "Permutation similarity"? "Ordinary matrix similarity"? ad 2.: Of course you are right, I will remove "probably" in the last question. – Hans Stricker Jan 13 '10 at 7:21