From: mjd@op.net (Mark-Jason Dominus) Newsgroups: comp.theory,comp.programming,sci.math Subject: Elementary problem in graph theory Date: 17 Mar 1996 17:34:08 -0500 Keywords: composition Leeuwenhoek Nordhoff quench It's a desirable property of computer networks that the topology of the network look the same, no matter what node you're at. n-cube networks, complete networks (every computer connected to every other,) and ring networks all have this proprty. Let's model networks with graphs, and say that a graph G(V,E) is `uniform' when For all u,v in V, There exists an automorphism A of G for which A(u) = v. That is, the network looks the same from u as it does from v, because you can change u into v just by renaming the vertices as described by A. Here's what I want to know: * What is this `uniformity' property usually called? * Given a graph G, what is an efficient way to compute whether or not it has this property? * What properties are related to this one? I've pointed followups into comp.theory. ============================================================================== Date: Wed, 27 Mar 96 12:51:24 CST From: rusin (Dave Rusin) To: mjd@op.net Subject: Re: Elementary problem in graph theory Newsgroups: comp.theory,comp.programming,sci.math In article <4ii410$7oh@monet.op.net> you write: >Let's model networks with graphs, and say that a graph G(V,E) is >`uniform' when > > For all u,v in V, > There exists an automorphism A of G > for which A(u) = v. > >That is, the network looks the same from u as it does from v, because >you can change u into v just by renaming the vertices as described by A. > >Here's what I want to know: > > * What is this `uniformity' property usually called? I don't know, but I would phrase it by saying that the automorphism group of G is vertex-transitive. By analogy with topology I suppose you could call G homogeneous. > * Given a graph G, what is an efficient way to compute whether > or not it has this property? I don't know. Someone asked the more specific question of whether or not a graph is a Cayley diagram; Cayley diagrams are specific examples of such graphs and for all I can tell these are the only such examples. I would be interested in hearing about a test to determine whether or not a graph is indeed a Cayley diagram; a partial solution is below. > * What properties are related to this one? A Cayley diagram is formed from a (usually finite) group X and a collection of elements x_i in X. One makes a (directed) graph G from this information by taking one vertex for each group element in X, and drawing an edge from the vertex g to the vertex h if h = g x_i for one of those preselected group elements x_i. Given two vertices g and h, there certainly is an automorphism of the graph G carrying g to h, namely, the automorphism sending each vertex k to the vertex (hg^(-1))k. It's a digraph automorphism because the presence of an edge from k to k' requires k'=k x_i for some i, whence ((hg^(-1))k') = ((hg^(-1))k)x_i by the associative law, so that (hg^(-1))k' and (hg^(-1))k are indeed also connected by an edge. Given a vertex-transitive graph G, you can attempt to describe it as a Cayley diagram. Let X be the automorphism group of G. If X contains no automorphisms which fix a given vertex v0, then X is in one-to-one correspondence with G (namely an automorphism x in X may be paired with the vertex x(v0); the transitivity and absence of vertex-fixers make this a one-to-one correspondence). v0 will correspond to the identity element of X in this way. Within the group X we can find the elements x_i corresponding to vertices linked to x0 by an edge. Then if u and v are vertices of G joined by an edge, and if they correspond respectively to group elements x and y (i.e., u = x(v0), v=y(v0)), then since x^(-1) is a _graph_ isomorphism which happens to carry u to v0 and v to x^(-1)y (v0), there must be an edge between v0 and x^(-1)y(v0), so that x^(-1)y is one of the x_i, i.e., y = x x_i. Thus such a graph really is a Cayley diagram of the group G and the generators x_i. (In the absence of a direction on the edges, you are including x_i^(-1) whenever you include x_i). So all the graphs you are interested in are really Cayley graphs in disguise _if_ you know that the stabilizer of one (hence any) point is trivial. I don't see any easy way to take, say, the complete graph on three vertices (whose automorphism group is Sym(3) of order 6) and recognize that it's the Cayley graph on the cyclic group of order 3. You can try looking for _subgroups_ of Aut(G), but you need to know that you can _choose_ automorphisms of G carrying each vertex to another in a consistent way. These more general vertex-transitive graphs can certainly be described by a generalization of the procedure used to construct Cayley graphs: given a group X, some generators x_i, _and_ a subgroup H, one makes a graph with one vertex for each coset Hx of H in X, and as before joins them with an edge if Hx' = Hxx_i for some i. Every vertex-transitive graph is isomorphic to such a thing, using X = Aut(G) and H = Stab(v0). What I don't see right offhand is any examples of these more general things which don't already arise as ordinary Cayley diagrams. Anyway, it would certainly appear that your problem reduces to group theory. dave ============================================================================== Date: Wed, 3 Apr 1996 14:43:04 -0500 (EST) From: Mark-Jason Dominus To: Dave Rusin Subject: Re: Elementary problem in graph theory On Wed, 27 Mar 1996, Dave Rusin wrote: > I don't know. Someone asked the more specific question of whether or not > a graph is a Cayley diagram; Cayley diagrams are specific examples of > such graphs and for all I can tell these are the only such examples. Please let me know what you think of the following: Consider the following graph: Vertices: 0 , 1 , 2 , 3 , 4 0', 1', 2', 3', 4' Edges: Pentagon Pentagon' Cross-edges 0--1 0'--1' 0--0' 1--2 1'--2' 1--2' 2--3 2'--3' 2--4' 3--4 3'--4' 3--1' 4--0 4'--0' 4--3' This graph contains two pentagons (the two columns on the left) with each vertex on one pentagon conntected to one of the vertices in the other pentagon (The right column above.) It is vertex-transitive. This graph has 10 vertices; if it is a Cayley graph, then it is the Cayley graph of some group G with 10 elements. The only possibilities are Z10 and D5. Let 'a' be the element of G which corresponds to the edge 0--1. Therefore, we have aaaaa=1 because of graph automorphisms and 0--1--2--3--4--0. Let 'b' be the element of G which corresponds to the edge from 0--0'. Therefore, we have bb=1. similarly, because of 0--0'--0. The graph contains the path 0-a-1-b-2' and also 0-b-0'-a-1'-a-2', so we have ab=baa. But this doesn't happen in either Z10 or in D5. (In Z10 we have ab=ba, and in D5 we have ab=baaaa. Either of these, combined with {aaaaa=1, bb=1, ab=baa}, implies a=1.) So G is not a Cayley graph at all. > If X contains no automorphisms which fix a given vertex v0, then ... This condition doesn't hold for G; there are twelve automorphisms fixing any given vertex. > Anyway, it would certainly appear that your problem reduces to group theory. Indeed. Thanks a lot for taking so much time and trouble to write me about it. I'd seen Cayley graphs many years ago as a curiosity, and then forgotten about them. If I went awry in showing that G above is a vertex-transitive non-Cayley graph, please do let me know. Mark-Jason Dominus mjd@plover.com