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 bedon't have to be isomorphic, but maybe something weaker?)
Best Answer
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.