# Non-isomorphic graphs with identical iterated degree matrix

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

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.
• @JacquesCarette we fix only the the degree of vertex $n$, not other vertices. And this all makes sense only for large $n$. Jul 20 at 9:57