Talk:Graph automorphism

This  level-5 vital article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

[1]

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

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

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

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

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

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

Is there a mistake in the claimed inclusion relationship between t-transitive graphs and arc-transitive graphs? It was pointed out elsewhere that any star graph is 2-transitive but not arc-transitive. Or do I misunderstand the terminology? —St.Nerol (talk, contribs) 19:00, 25 May 2024 (UTC)Reply