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


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

  • $\begingroup$ I don't understand the construction: take n=2, so V={1,2}, vertex 1 has degree 0, sure, vertex 1 has degree 1... how? Connected to what other vertex? $\endgroup$ Jul 20, 2022 at 6:58
  • $\begingroup$ @JacquesCarette we fix only the the degree of vertex $n$, not other vertices. And this all makes sense only for large $n$. $\endgroup$ Jul 20, 2022 at 9:57
  • $\begingroup$ Oh, I misunderstood, I thought you meant vertex i has degree i-1 -- this makes much more sense! $\endgroup$ Jul 20, 2022 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.