Graph isomorphism and "level degree" sequences 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.
A: 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.
