Talk:Graph automorphism
From Wikipedia, the free encyclopedia
[edit] Group representation as graph automorphism group
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)
- 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)
[edit] counting automorphisms of rings
- 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)
