# Generalized degree spectrum

A standard graph invariant is the degree sequence, but it is well-known, that the degree sequence is not a complete graph invariant, i.e. a graph cannot be reconstructed uniquely from its degree sequence.

That means: the degree sequence contains too little information about the graph. But what about generalizations of the degree sequence, containing more information but still relying on degrees only, i.e. counting?

Let $G$ be a undirected graph with $n$ nodes.

[B0] Consider the set $D^0 = [n]^{[1]}$ of all functions $d^0:[1] \rightarrow [n]$ and assign to each $d^0 \in D^0$ the number of vertices with degree $d^0_i = d^0$ (precisely $d^0_i = d^0(1)$).

[C0] This yields a function $D_G^1: D^0 \rightarrow [n]$, which bears the same information as the degree sequence. Let's call it degree spectrum. Note, that it takes into account only the 1-neighbourhood of each node.

[A1] Consider for each node $v_i$ the function $d^1_i: D^0 \rightarrow [n]$ assigning to each $d^0 \in D^0$ the number of its neighbours with degree $d^0_j = d^0$.

[B1] Consider the set $D^1 = [n]^{D^0}$ of all functions $d^1: D^0 \rightarrow [n]$ and assign to each $d^1 \in D^1$ the number of vertices with $d^1_i = d^1$.

[C1] This yields a function $D_G^2: D^1 \rightarrow [n]$, which is another graph invariant, taking into account the 2-neighbourhood of each node.

This process can be continued:

[Ak+1] Consider for each node $v_i$ the function $d^{k+1}_i: D^k \rightarrow [n]$ assigning to each $d^k \in D^k$ the number of its neighbours with $d^k_j = d^k$

[Bk+1] Consider the set $D^{k+1} = [n]^{D^k}$ of all functions $d^{k+1}: D^k \rightarrow [n]$ and assign to each $d^{k+1} \in D^{k+1}$ the number of vertices with $d^{k+1}_i = d^{k+1}$.

[Ck+1] This yields a function $D_G^{k+2}: D^{k+1} \rightarrow [n]$, which is another graph invariant, taking into account the k+2-neighbourhood of each node.

Question: Has this kind of generalized degree spectrum already been investigated? Under which name?

If it not has been investigated already I will feel free to continue this post, otherwise I will stop here.

-

This sort of thing occurs under the name of "stable coloring" in Section 2.2 of Martin Otto's book "Bounded Variable Logics and Counting: A Study in Finite Models". (I don't have the book handy at the moment, so I'm copying the reference from a paper that cites it; I hope it's correct.) I vaguely recall having seen other names for this construction as well, probably the names of the inventor (or re-inventor), but I don't remember the name; you can probably find a reference in Otto's book.

-

Thanks to Andreas' hint I found this slide show by Martin Fürer: Combinatorial Methods for the Graph Isomorphism Problem. On slide 4 he treats vertex classiﬁcation which is exactly similar in spirit to what I tried to sketch here (but expressed in three lines only):

Algorithm:

Start: Color the vertices by their degree.

Loop: Color the vertices by the multiset of colors of their neighbors.

Stop: When the color partition stabilizes.

So I am going to stop this thread here.

-

For the record: A paper from which you can learn a lot about vertex classification, the $k$-dim Weisfeiler-Lehman method and its history is: An Optimal Lower Bound on the Number of Variables for Graph Identification (1992) by Jin-yi Cai , Neil Immerman , Martin Fürer.

-