[next] [prev] [up] Date: Thu, 08 Dec 94 15:21:04 -0500
[next] [prev] [up] From: Jerry Bryan <BRYAN@wvnvm.wvnet.edu >
[next] [prev] [up] Subject: Re: Cayley Graphs
On 12/07/94 at 20:46:00 Martin Schoenert said:

The Cayley graph Gamma for a group G generated by a certain system of
generators < g_1, g_2, ... > is defined as follows.

>The vertices of Gamma correspond to the elements of G.  From vertex v_1
>draw an edge to v_2 labelled with g_i, if and only if v_1 g_i = v_2.
>Also draw an edge from v_2 to v_2 labelled g_i^-1 (or g_i').

So the Cayley graph depends on the group *and* on the generating system.
Simple, isn't it.

These are fine points, but they bother me anyway.

1. Suppose I write <Q>=<Q,H>. If I mean that the group <Q> is equal
to the group <Q,H>, then the equation is correct. If I mean that
the Cayley graph of <Q> is the same as the Cayley graph of <Q,H>,
then the equation is incorrect. Which is the conventional meaning?
Is the meaning universal, or does it depend on the author and the

2. I gather from your note and from things that Dan sent me that
one should not list inverses of the generators. For example,
<U,R> is sufficient and one should not write <U,U',R,R'>. But
people conventionally write <Q> which includes six processes and
their six inverses. Is this acceptable usage, or should we write
<U,D,L,R,F,B> instead?

As an additional comment, I have frequently written about the Q length
of a process in <U,R> or the Q+H length of a process in <U,R>. I think
we would be better served to talk about the length of a process in
<U,R> or the length of a process in <U,U2,R,R2> if the generator
notation implies a particular Cayley graph.

 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan)                        (304) 293-5192
Associate Director, WVNET                            (304) 293-5540 fax
837 Chestnut Ridge Road                              BRYAN@WVNVM
Morgantown, WV 26505                                 BRYAN@WVNVM.WVNET.EDU

[next] [prev] [up] [top] [help]