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?)