most recent 30 from http://mathoverflow.net 2013-05-24T13:58:58Z http://mathoverflow.net/feeds/question/24357 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24357/complete-vertex-invariants Hans Stricker 2010-05-12T10:06:55Z 2010-05-13T21:59:11Z

<p>This question is related to <a href="http://mathoverflow.net/questions/11531/yet-another-graph-invariant-the-similarity-matrix" rel="nofollow">Yet another graph invariant: the similarity matrix</a>.</p> <p>In graph theory there is much talk and research on <em>graph</em> invariants, especially complete graph invariants describing a graph up to isomorphism.</p> <p>I have the impression that there is only little talk and research on complete <em>vertex</em> invariants describing vertices (in their graph) up to conjugacy.</p> <p>One vertex invariant which is complete by definition is the smallest <em>n</em>-neighbourhood of a vertex <em>v</em> which distinguishes it from all vertices not conjugate to it. Let the <em>n</em>-neighbourhood of <em>v</em> be the (unlabelled but rooted) induced subgraph containing <em>v</em> (as the distinguished node) and all vertices at most <em>n</em> edges away from <em>v</em>.</p> <blockquote> <p>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 <em>do</em> attract attention? Then: Can some references be given?</p> </blockquote> <p>One reason why they <em>could</em> deserve attention is that complete vertex invariants might be used to define complete graph invariants (à la degree sequence, which is not complete, of course).</p>

http://mathoverflow.net/questions/24357/complete-vertex-invariants/24544#24544 Tony Huynh 2010-05-13T21:59:11Z 2010-05-13T21:59:11Z

<p>I think the main reason why they have not attracted much attention is due to <a href="http://en.wikipedia.org/wiki/Vertex-transitive_graph" rel="nofollow">vertex-transitive graphs</a>. 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. </p> <p>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}$. </p>