### 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 matrixiff there is a graph $G$ such that $S = \Sigma(G)$.

### Questions

Is the notion of

$n$-neighbourhoodtreated 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?)