### 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](http://mathworld.wolfram.com/GraphEccentricity.html) 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?)
> 
> 
> 



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*.


