Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Complete vertex invariants

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

Hans-Peter Stricker
  • 9.7k
  • 5
  • 53
  • 113