Graph isomorphism and "level degree" sequences

Question

Given a connected undirected graph $G=\{V,E\}$ of order $n$, let's build for each $v_i\in V$ a list corresponding to the number of newly discovered vertices at each level during a BFS traversal. For example, suppose our graph $G$ is:

This computation results in:

Node:
A: (3, 2)     // First level: (B, C, D). Second level: (E, F)
B: (3, 1, 1)  // First level: (A, C, E). Second level: (D). Third level: (F)
C: (2, 2, 1)  // First level: (A, B). Second level: (D, E). Third level: (F)
D: (3, 2)     // First level: (A, E, F). Second level: (B, C).
E: (2, 3)     // First level: (B, D). Second level: (A, C, F).
F: (1, 2, 2)  // First level: (D). Second level: (A, E). Third level: (B, C).

You can now remove the labels and build a set $S_G=\{(3, 2), (3, 2), (2, 3), (3, 1, 1), (2, 2, 1), (1, 2, 2)\}$ that characterizes the graph (non-uniquelly, I guess). I have written the elements of $S_G$ in ascending order of size first and descending lexicographical ordering next only for presentation purposes (to sort the vertices by gravity so to speak).

Does this representation/characterization/computation has a name? (or for counting newly discovered edges per-level instead of vertices, or both).

I'm curious to see two non-isomorphic graphs $G$ and $H$ where $S_G=S_H$. I have tried to build such $G$ and $H$ but haven't been able to.

Answer 1

In general, all attempts to solve graph isomorphism by identifying properties of vertices are thwarted by highly symmetric graphs.

So in this case, we can look for a graph for which this sequence will be as boring as possible. One option is to look for graphs with $2k$ vertices such that:

• Every vertex has degree $k$;
• The graph has diameter $2$. (Actually, this condition follows from the first; we don't need to take any special care to check it.)

Then, for every vertex, the sequence we get will be $(k, k-1)$.

For $k=3$, there are already two different graphs of this type: $K_{3,3}$ and the triangular prism graph. For large $k$, we get many more options. (For example, a search on House of Graphs found me fifteen different graphs for $k=6$, and those are just the ones that have properties someone thought were interesting.)

---

The paper Distinguishing vertices of random graphs by Bollobás considers these sequences, which it calls distance sequences. It is shown that for some random graph models (in particular, for $r$-regular graphs), almost all graphs you get will have the property that all $n$ vertices have different distance sequences.

This also has applications to graph isomorphism. Suppose that you compute the sets $S_G, S_H$ of distance sequences for two graphs $G$ and $H$. If they're different, then of course $G$ and $H$ are not isomorphic. But if $S_G = S_H$, and every element of $S_G$ is different, all you have to do is take the map $f : V(G) \to V(H)$ which sends a vertex $v \in V(G)$ to the unique vertex in $V(H)$ with the same distance sequence. This is the only possible candidate for an isomorphism between $G$ and $H$, and checking if it really is an isomorphism can be done quickly.