From: rusin@vesuvius.math.niu.edu (Dave Rusin) Newsgroups: sci.math Subject: Re: Q: simple graph theory Date: 17 Jan 1998 07:54:06 GMT In article <69oail$hnp$1@morgoth.sfu.ca>, nzhang@sfu.ca (Norman Zhang) wrote: > I have been trying to construct a simple graph (no loops or multiple > edges) that contains exactly three automorphisms with no success. Would > someone please give me some hint on this? An adjacency matrix is fine. > Thank you in advance. Here is a graph with symmetry group of order 3. Take three copies of this shape: * * | | *---* | /| | / | |/ | *---* and stand them up with their bottom edges forming a triangle; identify the side edges so that the middle edges touch to form a triangle, too, and the top points (there are only 3, not 6, after identification) stick out like three antennae. (The three of these shapes should have those slanted edges pointing in a consistent manner so that a 120-degree rotation of the top and bottom triangles is indeed a symmetry of the graph.) So there are three vertices each part of only one edge; these must be permuted under any automorphism. It follows that the set of vertices one edge away from these (the middle vertices) is also preserved as a class, and so of course the bottom three vertices are preserved setwise. This much reduces the symmetry group to lie in S_3 x S_3 x S_3 rather than S_9. Next note that each of the three middle vertices is adjacent to precisely one top vertex, and is _not_ adjacent to only one bottom vertex. Thus any permutation must preserve these {top, middle, bottom} triples, i.e, the symmetry group lies in the diagonal subgroup S_3 \equiv Diag(S_3) \in S_3 x S_3 x S_3. It's clear however that the permutation corresponding to a transposition in this isomorphism is not a symmetry of the graph (the slanted edges are not preserved), so the symmetry group is a proper subgroup of S_3 which clearly includes A_3, and so it _is_ A_3. So this graph has 3 symmetries. I don't know to what extent my example is minimal. Must be close if not best. dave PS - someone suggested looking at >Let V_1 = {v | f(v)!= v but f(f(v))=v} but this set is empty. Every orbit of a group action is G-isomorphic to the coset space G/Stab(v), which in English means the number of translates of each vector in this setting must be 1 or 3. ============================================================================== From: cet1@cus.cam.ac.uk (Chris Thompson) Newsgroups: sci.math Subject: Re: Q: simple graph theory Date: 18 Jan 1998 17:10:59 GMT In article <69po2u$ra6$1@gannett.math.niu.edu>, Dave Rusin wrote: >In article <69oail$hnp$1@morgoth.sfu.ca>, nzhang@sfu.ca (Norman Zhang) wrote: > >> I have been trying to construct a simple graph (no loops or multiple >> edges) that contains exactly three automorphisms with no success. Would >> someone please give me some hint on this? An adjacency matrix is fine. >> Thank you in advance. > >Here is a graph with symmetry group of order 3. > >Take three copies of this shape: > >* * >| | >*---* >| /| >| / | >|/ | >*---* > >and stand them up with their bottom edges forming a triangle; identify >the side edges so that the middle edges touch to form a triangle, too, >and the top points (there are only 3, not 6, after identification) stick >out like three antennae. > >(The three of these shapes should have those slanted edges pointing in >a consistent manner so that a 120-degree rotation of the top and bottom >triangles is indeed a symmetry of the graph.) [...] This produces a graph with 9 vertices and 15 edges, but unfortunately it has automorphism group S_3, not C_3, if I have followed the above description correctly. >I don't know to what extent my example is minimal. Must be close if not best. It would have been (co-)minimal if it had been correct! There are two graphs with 9 vertices and 15 edges and automorphism group C_3: * * /-------\ /|\ / \ | | / | \ / \ /-*-* --*-\ * | *-----* | | \ / | | \ | / \ / | \ * * | \|/ \ / | \ / \ / | *-----* | *---* | | /| | | | | | /-/ | \ * | / |/ | \ \ / / *-----* \--*--/ [ObApology for ASCII art!] That these are minimal is due to Meriwether (1963, unpublished?) and Harary & Palmer (1966, Czech Math J 16,70-71). There are several other C_3 graphs with 9 vertices and >15 edges, or 15 edges and >9 vertices. It is a nice old result due to Frucht that every finite group G is the automorphism group of some finite graph. Sketch of proof: form the Cayley "colour-graph" of G, i.e. a set of vertices corresponding to the elements of G, and for each pair of elements g,h a directed edge from v(g) to v(h) coloured according to the value of g^{-1}h. It is easy to see that the automorphisms of this digraph which preserve the colours of the edges form a group isomorphic to G. Now replace directed edges of each colour from a suitable set of distinct assymetric graphs; e.g. those of the k'th colour by * * | | | *---*-(...)-* (2k-1 edges) \|/ => | | *---*-(...)-*---* (2k edges) | | * * Then the resulting (uncoloured, undirected) graph can be seen to also have automorphism group isomorphic to G. The above construction makes unnecessarily large graphs, of course. For example, its sufficient to pick a set of generators for G and to include the directed edge from v(g) to v(h) only when g^{-1}h is one of the set. If you do that for C_3, you end up with the 18-vertex 18-edge graph: * | * * | | *---*---*---* \ / *--*--* *--* \ / *--* *--*--* \ / * which has some independant interest as being the smallest C_3 graph with only one cycle (and hence no more edges than vertices: it's easy to see that no tree can have automorphism group C_3). Chris Thompson Email: cet1@cam.ac.uk ============================================================================== Date: Sun, 18 Jan 1998 14:46:33 -0600 (CST) From: Fred Galvin To: Dave Rusin Subject: Re: Q: simple graph theory On Sun, 18 Jan 1998, Dave Rusin wrote: > Did my graph have too many symmetries or too few? (I thought I had gotten > it right, but this was not something I'd thought about before.) It's > certainly possible I just failed to communicate it properly (the intended > graph has 9 vertices and 15 edges). I wasn't quite sure I understood your construction. Here's my interpretation. Vertices Edges Top g h i dg eh fi Middle d e f de ef fd ad be cf ae bf cd Bottom a b c ab bc ca If this is the graph you had in mind, its automorphism group is S_3; every permutation of {g,h,i} extends to an automorphism. To get a symmetrical drawing, put a, d, c, f, b, e (in that order) at the vertices of a regular hexagon. For instance, the permutation a b c d e f g h i a c b e d f h g i is an automorphism of order two. > If this is a "canonical homework problem" does that mean there's a > canonical answer? I don't know if it's a "canonical homework problem"; this is only the third time in my life I've taught graph theory, so I'm no expert. However, it seems there are two canonical answers. According to Frank Harary's _Graph Theory_, the smallest graphs with automorphism group C_3 have 9 vertices and 15 edges, and there are two of them. The one shown on p. 170 of Harary's book is a triangulation of the 9-gon: draw a regular 9-gon with vertices 0,1,2,3,4,5,6,7,8, and add the chords 02,03,35,36,68,60. Exercise 14.4 on p. 176 is to find the other one. I haven't tried to find it, but I know where to look it up: the reference is F. Harary and E. M. Palmer, The smallest graph whose group is cyclic, Czech. Math. J. 16 (1966), 70-71. Fred ============================================================================== From: spear@empty.set (David Spear) Newsgroups: sci.math Subject: Re: Q: simple graph theory Date: Wed, 21 Jan 1998 02:05:13 -0400 In article <6a0l25$1ci@staff.cs.su.oz.au>, ftww@cs.su.oz.au Geoff Bailey (Fred the Wonder Worm) wrote: > In article , > David Spear wrote: > > > >However I think the example can be fixed by ... > > > > ... > > Unfortunately not. > > ... > > ... it clearly has at least S_3 as the symmetry group. > ( ... exactly S_3 as their symmetry group ... , in fact.) > > Cheers, > Geoff. > Here is a true fix to Dave Rusin's example: * * | /| | / | | / | * / * | / - | | / - | |/- | *-------* with identifications the same as for Dave Rusin's original graph. Note the vertex degrees -- top vertices have degree 2, middle vertices have degree 3 and bottom vertices have degree 5. Any automorphism must take tops to tops, middles to middles and bottoms to bottoms. Thus as Dave Rusin argued, the automorphism group is at most S_3 x S_3 x S_3. Using the fact that an automorphism must be distance preserving I convinced myself that this graph has only three automorphisms. But to be doubly sure I wrote a short Maple program to determine which of the 6^3 possible permutations in S_3 x S_3 x S_3 are automorphisms. Maple produced exactly 3 automorphisms, hence the automorphism group must be A_3. Dave Rusin's example and explanation, though flawed, provided a clear structure for analyzing the problem and led (after a few tries) to a simple fix. Thanks to all on this thread -- I am a graph theory novice and what may be for some an easy problem was for me challenging, educational and fun. -- David Spear ============================================================================== Subject: Graphs with automorphism group C_3 To: rusin@math.niu.edu (Dave Rusin), Hoey@AIC.NRL.Navy.Mil (Dan Hoey), W.Taylor@math.canterbury.ac.nz (Bill Taylor) Date: Thu, 22 Jan 1998 12:46:10 +0000 (GMT) From: Chris Thompson Dave, Dan, Bill, Thank you each for your messages. I'm afraid I haven't had time to catch up on sci.math matters since the weekend... Dan points out that my second 9-vertex 15-edge graph has automorphism group S_3, not C_3... > Last night I said the automorphism group of the second was C_2 x C_3, > but of course it's S_3. > > > /-------\ > > | | > > /-1-2 --4-\ > > | | \ / | | > > | \ 3 5 | > > | \ / \ / | > > | 9---6 | > > | | | | > > \ 8 | / > > \ \ / / > > \--7--/ > > > > Then the vertex permutation (1,3)(4,9)(5,8)(6,7) is an automorphism. > > Is there really a second 9 vertex 15 edge S3 graph? > > Any permutation of {2,5,8} is possible; odd permutations exchange > the sets {1,4,7} and {3,6,9}. Yes, you are quite correct. Isn't it hard to see these automorphisms of order 2 unless you draw the graph right? :-( > I'd write your first graph as at left below. > > *-----* > \ / \ > \ / \ > *-----*-----* > / \ / \ / > / \ / \ / > *-----*-----* > \ / > \ / > * Much nicer than my attempt! > I'd still like to know if there is another 9-vertex, 15-edge graph > with exactly three automorphisms. Well, I'm beginning to wonder. Harary "Graph Theory" (Addison-Wesley, 1969) says there is: # Exercise 14.4: Construct a graph of 9 points and 15 lines (different from # Fig. 14.7) whose group is cyclic of order 3. (Harary and Palmer [HP3]) where the reference is # [HP3] F. Harary and E.M. Palmer, The smallest graph with whose group is # cyclic, Czech. Math, J. 16 (1966), 70-71 I've got other textbooks and lecture notes referencing the same paper, but they all display only the first graph (in many geometrically different arrangements). I know I've had difficulty in the past finding the second graph, as indeed I did on this occasion, and now begin to wonder whether I just went on searching until I found one in which I missed the involution... Bill writes: > As usual, Chris Thompson has said the last word on the topic. Far from it, as you can see above! > However, I'll just add this tiny nitpick addendum anyway. > > cet1@cus.cam.ac.uk (Chris Thompson) writes: > > |> >Here is a graph with symmetry group of order 3. > ... ... > |> If you do that for C_3, you end up with the 18-vertex 18-edge graph: > |> > |> * > |> | > |> * * > |> | | > |> *---*---*---* > |> \ / > |> *--*--* *--* > |> \ / > |> *--* *--*--* > |> \ / > |> * > |> > |> which has some independant interest as being the smallest C_3 graph with > |> only one cycle > > > Smallest EQUAL, in fact. There is also this one: > > > * * * > | |/ > *---*---*---* > \ / > *--* *--* > / \ / > * * *--* > / \ / \ > * * * Ah, I'm OK on this one! That has group C_3 x C_2 x C_2 x C_2. You have mised the switching of the pairs of terminal vertices at the end of the V's. Chris Thompson Email: cet1@cam.ac.uk ============================================================================== From: Fred Galvin Newsgroups: sci.math Subject: Re: Q: simple graph theory Date: Sat, 24 Jan 1998 21:03:55 -0600 On 18 Jan 1998, Chris Thompson wrote: > [...] > It would have been (co-)minimal if it had been correct! There are two graphs > with 9 vertices and 15 edges and automorphism group C_3: > > * * /-------\ > /|\ / \ | | > / | \ / \ /-*-* --*-\ > * | *-----* | | \ / | | > \ | / \ / | \ * * | > \|/ \ / | \ / \ / | > *-----* | *---* | > | /| | | | | > | /-/ | \ * | / > |/ | \ \ / / > *-----* \--*--/ > > [ObApology for ASCII art!] That these are minimal is due to Meriwether > (1963, unpublished?) and Harary & Palmer (1966, Czech Math J 16,70-71). The graph on the left is indeed 3-cyclic (its automorphism group is cyclic of order 3), but the one on the right has automorphisms of order 2. In fact, it seems that the one on the left is the *unique* 3-cyclic graph with 9 vertices and 15 edges. In the paper you cited, Harary & Palmer claimed that there were *three* such graphs: the correct example (which they called M_3) and two others. A few years later they retracted this claim [F. Harary and E. M. Palmer, Correction, Czechoslovak Math. J. 21 (1971), 180], saying "[t]his error was kindly pointed out to us by Professor ROBERTO FRUCHT, who is setting the record straight in his forthcoming paper . . . with BOUWER." That M_3 is the *unique* smallest 3-cyclic graph is asserted without proof on p. 55 of Izak Z. Bouwer and Roberto Frucht, Line-minimal graphs with cyclic group, in: J. N. Srivistava et al., eds., _A Survey of Combinatorial Theory_ (North-Holland, 1973), 53-67. The uniqueness proof was supposed to appear in a forthcoming work of Frucht and others; if it did come forth, the reference should be easy enough to find, but I didn't have time to look for it.