Complete vertex invariants

Question

This question is related to Yet another graph invariant: the similarity matrix.

In graph theory there is much talk and research on graph invariants, especially complete graph invariants describing a graph up to isomorphism.

I have the impression that there is only little talk and research on complete vertex invariants describing vertices (in their graph) up to conjugacy.

One vertex invariant which is complete by definition is the smallest n-neighbourhood of a vertex v which distinguishes it from all vertices not conjugate to it. Let the n-neighbourhood of v be the (unlabelled but rooted) induced subgraph containing v (as the distinguished node) and all vertices at most n edges away from v.

Can someone explain in a few words, why complete vertex invariant(s) seem not to deserve so much attention? Or am I wrong and they do attract attention? Then: Can some references be given?

One reason why they could deserve attention is that complete vertex invariants might be used to define complete graph invariants (à la degree sequence, which is not complete, of course).

Answer 1

I think the main reason why they have not attracted much attention is due to vertex-transitive graphs. In the case that $G$ is vertex-transitive, then $V(G)$ consists of a single conjugacy class. Thus, complete vertex invariants will be of no help in constructing the automorphism group of $G$. The other extreme is if $aut(G)$ is trivial, so in this case each vertex is a separate conjugacy class.

A potential middle ground is to look at all graphs $G$ such that the union of the non-singleton conjugacy classes of $G$ has size at most $k$. Let $\mathcal{G}$ be the set of all such graphs. Here, complete vertex invariants might be useful for constructing the automorphism group of $G$. In general, I have to check $|V(G)|!$ potential permutations, but for graphs in $\mathcal{G}$, I only need to check at most $k!$. If I view $k$ as a constant, then as long as I can construct complete vertex invariants efficiently, this gives me a fast algorithm to construct $aut(G)$ for graphs in $\mathcal{G}$.