From: vdbuss@cs.indiana.edu (Jan Van den Bussche) Subject: Re: graphs with alternating group Date: 21 Jun 1999 06:58:45 GMT Newsgroups: sci.math.research To: sci-math-research@moderators.isc.org Forget my previous message about the existence of graphs on n vertices whose automorphism group is A_n---such graphs don't exist, and this is embarrassingly easy to see. A_n can map any pair to any other pair (for n not too small, that is). Hence if a graph has all even permutations as automorphisms, then in fact it has all permutations as automorphisms. --Jan Van den Bussche ============================================================================== From: Robin Chapman Subject: Re: graph with alternating group Date: Mon, 21 Jun 1999 08:20:10 GMT Newsgroups: sci.math.research To: sci-math-research@moderators.isc.org In article <7ki4d1$of9$1@flotsam.uits.indiana.edu>, vdbuss@cs.indiana.edu (Jan Van den Bussche) wrote: > Can anyone give me an example of a graph on the n nodes 1, ..., n > that has the alternating group A_n as its group of automorphisms? > > Does such a graph exist for arbitrary large n? > No and no. I presume one is talking about simple graphs. The only way a graph on n vertices could have A_n as automorphism group is for A_n to act in the natural way on the vertices. But A_n is transitive on the set of possible edges, so the graph has no edges or is complete and has S-n as automorphisms. If one considers directed graphs, then rather trivially one can construct examples when n = 2 (one directed edge) or n = 3 (a directed cycle) but not for n >= 4, since A_n is transitive on ordered pairs of distinct vertices. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "They did not have proper palms at home in Exeter." Peter Carey, _Oscar and Lucinda_ Sent via Deja.com http://www.deja.com/ Share what you know. Learn what you don't.