发帖
雷达卡
Wenjun Xiao Behrooz Parhami
Dept. of Computer Science Dept. of Electrical & Computer Engineering
South China University of Technology, and University of California
Dept. of Mathematics, Xiamen University Santa Barbara, CA 93106-9560, USA
wjxiao@scut.edu.cn parhami@ece.ucsb.edu
Abstract
Hexagonal mesh and torus, as well as honeycomb
and certain other pruned torus networks, are known
to belong to the class of Cayley graphs which are
node-symmetric and possess other interesting
mathematical properties. In this paper, we use
Cayley-graph formulations for the aforementioned
networks, along with some of our previous results on
subgraphs and coset graphs, to draw conclusions
relating to internode distance and network diameter.
We also use our results to refine, clarify, and unify a
number of previously published properties for these
networks and other networks derived from them.
Keywords– Cayley digraph, Coset graph, Diameter,
Distributed system, Hex mesh, Homomorphism,
Honeycomb mesh or torus, Internode distance.
1. Introduction
The fact that Cayley (di)graphs and coset graphs
are excellent models for interconnection
networks, of the types studied in relation to
parallel processing and distributed computation,
is widely acknowledged [1], [2], [4]. Many
well-known, and practically significant,
interconnection networks are Cayley (di)graphs
or coset graphs. For example, hypercube (binary
q-cube), butterfly, and cube-connected cycles
networks are Cayley graphs, while de Bruijn
and shuffle-exchange networks are instances of
coset graphs [4], [11].
Much work on interconnection networks can be
categorized as ad hoc design and evaluation.
Typically, a new interconnection scheme is
suggested and shown to be superior to some
previously studied network(s) with respect to one
or more performance or complexity attributes.
Whereas Cayley (di)graphs have been used to
explain and unify interconnection networks with
many ensuing benefits, much work remains to be
done. As suggested by Heydemann [4], general
theorems are lacking for Cayley digraphs and
more group theory has to be exploited to find
properties of Cayley digraphs.
In this paper, we explore the relationships
between Cayley (di)graphs and their subgraphs
and coset graphs with respect to subgroups and
formulate general results on homomorphism and
diameter formulas between them. We provide
several applications of these results to well-known
interconnection networks such as hexagonal torus,
honeycomb torus, and several other classes of
pruned torus networks.
Before proceeding further, we introduce some
definitions and notations related to (di)graphs in
general, Cayley (di)graphs in particular, and to
interconnection networks. For more definitions
and mathematical results on graphs and groups we
refer the reader to [3], for instance, and on
interconnection networks to [6], [8]. Unless noted
otherwise, all graphs in this paper are undirected.
Proofs are omitted here and will be provided in a
more complete version of this paper.
strongHexagonalstrong and Pruned Torus Networks as Cayley Graphs.pdf
(3.07 MB, 需要: 22 个论坛币)
提升卡
置顶卡
沉默卡
变色卡
抢沙发
千斤顶
显身卡
京公网安备 11010802022788号
