Talk:Graph automorphism

This is the talk page for discussing improvements to the Graph automorphism article.
This is not a forum for general discussion of the article's subject.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Article policies

Find sources: Google (books · news · scholar · free images · WP refs) · FENS · JSTOR · TWL

[1]

About the definition[edit]

I think there is an issue with infinite graphs. For example let's take the following graph :

         u    u'
    o    o    o    o   
...           |    |    ...
    o    o    o    o   
         v    v'

and consider this transformation

            u    u'
    -> o -> o -> o -> o ->
...              |    |    ...
    -> o -> o -> o -> o ->
            v    v'

It verifies the conditions for being an automorphism (the image of an edge is an edge as well), but the inverse application doesn't (the image of (u',v') is not an edge). It's annoying because it implies that the set of automorphisms of this graph is not a group... Maybe I'm missing something, but otherwise the definition should be more restrictive to ensure inversibility even for infinite graphs. That is something like :

an automorphism of a graph G = (V,E) is a permutation σ of the vertex set V, such that (σ(u),σ(v)) is an edge if and only if (u,v) also is an edge.

Regards --198.252.153.244 (talk) 10:24, 29 October 2011 (UTC)[reply]

Yes, this is absolutely right -- the current statement implicitly assumes the graph is finite. I've fixed it. --Joel B. Lewis (talk) 21:20, 29 October 2011 (UTC)[reply]

Group representation as graph automorphism group[edit]

Does someone know, whether for every finite group there is a graph with a corresponding automorphism group? HenningThielemann (talk) 18:02, 29 June 2008 (UTC)[reply]

I believe that this can be shown for any group, finite or not, by replacing the edges of a Cayley graph of the group by subgraphs, using a different and distinguishable subgraph for each generator of the Cayley graph. See for instance some similar results quoted in the article on Johannes De Groot about representing any group as the automorphisms of a compact Hausdorff space or of a commutative ring. —David Eppstein (talk) 19:06, 29 June 2008 (UTC)[reply]

I have come across this theorem of Frucht in the Handbook of graph theory saying:

Given any group G, there exists infinitely many connected graphs X such that Aut(X) is abstractly isomorphic to G. Moreover, X may be chosen to be cubic.

the Frucht article in reference.
R.Frucht. Graphs of Degree 3 with given abstract group, Canad. J. Math. 3 1949.

This fact is somewhat interesting and relevant, should it be included? Genusfour (talk) 11:59, 4 September 2009 (UTC)[reply]

Done. — Radagast3 (talk) 07:50, 6 September 2009 (UTC)[reply]

counting automorphisms of rings[edit]

Abstract :

"We study the complexity of the isomorphism and automorphism problems for finite rings with unity. We show that both integer factorization and graph isomorphism reduce to the problem of counting automorphisms of rings. The problem is shown to be in the complexity class AM ¿ coAM and hence is not NP-complete unless the polynomial hierarchy collapses. Integer factorization also reduces to the problem of finding nontrivial automorphism of a ring and to the problem of finding isomorphism between two rings. We also show that deciding whether a given ring has a non-trivial automorphism can be done in deterministic polynomial time."

It is unclear to me whether all this have a consequence for the Graph automorphism#Graph automorphism problem. Also, I am tempted to add the result to Graph isomorphism#GI-hard problems, but I am cautioned by the lack of the full paper yet. Any opinions? Twri (talk) 16:52, 1 April 2009 (UTC)[reply]

Table of examples[edit]

Discussion on this is at Talk:Symmetric graph#Table of examples. – Radagast3 (talk) 12:15, 6 September 2009 (UTC)[reply]

Chevalley Groups[edit]

Just fyi, the term graph automorphism is actually used to describe outer automorphisms of Chevalley groups, which among other things help create the twisted Chevalley groups. I'd suggest this article be renamed to "Automorphism groups of graphs" while creating an article on "Graph automorphisms of Chevalley groups", and making the "Graph automorphism" page into a disambiguation page. —Preceding unsigned comment added by 86.202.223.192 (talk) 17:10, 12 December 2010 (UTC)[reply]

In my experience, the phrase is by far more frequently used to refer to automorphisms of graphs (and in any case, an automorphism is not a group, it is a member of a group). So I think the better way to handle this, per WP:PRIMARYTOPIC, is to leave this article at its present name, to create a new article on the Chevalley group meaning under some other name (e.g. "Graph automorphism (Chevalley groups)") and to create a hatnote at the top of this article pointing to the other one. —David Eppstein (talk) 00:10, 13 December 2010 (UTC)[reply]

Complexity[edit]

The discussion about the complexity of the problem is outdated due to Babai's advance on graph isomorphism.

Also, an NP problem does not have to be either polynomial or NP-Complete, it may also be intermediary. — Preceding unsigned comment added by 46.117.120.73 (talk) 13:10, 28 January 2017 (UTC)[reply]

What, specifically, in the discussion of the problem here, do you think is made outdated by Babai's results? —David Eppstein (talk) 18:37, 28 January 2017 (UTC)[reply]