Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!udel!haven.umd.edu!umd5!newton.cs.jhu.edu!stiller
From: stiller@cs.jhu.edu (Lewis Stiller)
Newsgroups: comp.theory
Subject: Re: group diagram
Keywords: Cayley graphs, group action graphs
Message-ID: <stiller.674341275@newton.cs.jhu.edu>
Date: 15 May 91 20:58:55 GMT
References: <9105151724.AA00274@poincare.crin.fr>
Reply-To: stiller@cs.jhu.edu (Lewis Stiller)
Organization: JHU Computer Science Department, Baltimore MD
Lines: 77

In article <9105151724.AA00274@poincare.crin.fr> Pierre Lescanne <lescanne%loria.crin.fr@VM1.NoDak.EDU> writes:
>Does someone knows a good reference on "Group diagram" also called
>"Cayley diagrams" or "Group graphs", especially with reference to
>algorithms?  

Hi. I'm biased because I use them, but I think that algorithmic
implications of group graphs and closely related group action graphs
will increase with the newer machines, many of whose interconnection
networks are group action graphs. For instance, a simple fact that
is not universally known is that the hypercube and torus are group
graphs so algorithms that use those networks are using group graphs;
of course, the group machinery is unnecessary for many algorithms.
A. Rosenberg and his group (v.i.) are real experts in this.
Anyway, here are just a few of the things you might find interesting:


@article{akers:groupgraphs,
author="S.B. Akers and B. Krishnamorthy",
title="On group graphs and their fault tolerance",
journal="IEEE Trans. Comput.",
volume="C-36",
pages="885-888",
year=1987
}
@techreport{annexstein:groupactiongraphs,
title="Group action graphs and parallel architectures",
author="Fred Annexstein and Marc Baum\-slag and {Ar\-nold} L. Ro\-senberg",
institution="University of Massachusetts",
number="COINS Technical Report 87-133",
year="1987"
}

(I heard they have a new edition. This is a really fun book...)
@book{white:1984,
address="New York",
author= "Arthur T. White",
title= "Graphs, groups, and surfaces",
publisher = "North-Holland/Elsevier",
city="New York",
year="1984"
}

@inproceedings{stiller:supercomputing,
author="Lewis Stiller",
title="Group graphs and computational symmetry on 
massively parallel architecture",
month="October",
year=1990,
booktitle= "Supercomputing '90",
}

@techreport{annexstein88,
author="Fred Annexstein and Marc Baumslag",
title="Hamiltonian circuits in {Cayley} digraphs",
institution="University of Massachusetts Computer and Information Science Department",
address="Amherst, MA",
number="COINS 88-40"
}

You might or might not be interested in this article which does
not explicitly discuss group graphs:

@article{hillis:1990,
author="Danny Hillis and Washington {Taylor IV}",
title="Expoiting symmetry in high-dimensional finite-difference calculations",
journal="Journal of Parallel and Distributed Computing",
year=1990,
volume=8,
number=1,
month="January",
pages="77-79"
}

I hope this helps a little. Good luck,

lewis
stiller@cs.jhu.edu