Mathematics – Combinatorics
Scientific paper
1994-12-17
Mathematics
Combinatorics
Revised version, 43 pages: added references to the literature, new results, extended computations, and replaced the section on
Scientific paper
We address the degree-diameter problem for Cayley graphs of Abelian groups (Abelian graphs), both directed and undirected. The problem turns out to be closely related to the problem of finding efficient lattice coverings of Euclidean space by shapes such as octahedra and tetrahedra; we exploit this relationship in both directions. In particular, we find the largest Abelian graphs with 2 generators (dimensions) and a given diameter. (The results for 2 generators are not new; they are given in the literature of distributed loop networks.) We find an undirected Abelian graph with 3 generators and a given diameter which we conjecture to be as large as possible; for the directed case, we obtain partial results, which lead to unusual lattice coverings of 3-space. We discuss the asymptotic behavior of the problem for large numbers of generators. The graphs obtained here are substantially better than traditional toroidal meshes, but, in the simpler undirected cases, retain certain desirable features such as good routing algorithms, easy constructibility, and the ability to host mesh-connected numerical algorithms without any increase in communication times.
Dougherty Randall
Faber Vance
No associations
LandOfFree
The degree-diameter problem for several varieties of Cayley graphs, I: the Abelian case does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The degree-diameter problem for several varieties of Cayley graphs, I: the Abelian case, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The degree-diameter problem for several varieties of Cayley graphs, I: the Abelian case will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-328322