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

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



  [1]: http://mathoverflow.net/questions/11531/yet-another-graph-invariant-the-similarity-matrix