Non-isomorphic graphs with identical iterated degree matrix

Question

If $G = (V, E)$ is a simple, undirected graph and $T \subseteq V$, let $$N(T) = \{v \in V: \{v, t\}\in E \text{ for some }t\in T\}.$$

Given $v\in V$ we let $N_0(v) = \{v\}$ and $N_{k+1}(v) = N_k(v) \cup N(N_k(v))$ for all $k\geq 1$. The iterated degree sequence of $v$, denoted by $(\text{deg}_k(v))_{k\in\omega}$, is defined by $$\text{deg}_k(v) = |N_k(v)|\text{ for every }k\in \omega.$$

To every finite graph $G = (V,E)$ we associate the iterated degree matrix $\mathbb{D}(G) \in \mathbb{N}^{n\times n}$ (where $n=|V|$) in the following way: for every $v\in V$, take the first $n$ elements of its iterated degree sequence; order these $n$-element integer vectors lexicographically, and put these lexicographically ordered vectors in the matrix.

Question. Are there finite $G_i = (V_i, E_i)$ for $i = 1,2$ with $|V_1| = |V_2|$, $G_1\not\cong G_2$, but $\mathbb{D}(G_1) = \mathbb{D}(G_2)$?

Answer 1

Yes. Consider all graphs with $V=\{1,\ldots,n\}$ for which the vertex $n$ has degree $n-1$. There are $2^{n^2/2+o(n^2)}$ isomorphism classes of such graphs. But $\deg_k(v)=n$ for all $v$ and all $k\geqslant 2$, thus there exist only at most $n^{n-1}$ distinct matrices.