3
$\begingroup$

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.

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.