摘要
Cayley图是由有限群导出的一类重要的高对称正则图 ,被认为是非常合适的互连网络拓扑结构 .而笛卡尔乘积则是从小规模的指定网络构造大规模网络的重要构造方法 .本文证明了Cayley图的笛卡尔乘积仍是Cayley图 .作为实例 ,指明循环网络、超立方体、广义超立方体、超环面和立方连通圈等都是Cayley图 .
Cayley graphs, which represent a category of symmetric and regular graphs derivable from finite groups, have been shown to be very suitable to serve as interconnection network topologies. As an operation of graphs, the Cartesian product is an important method in constructing larger networks from some small and specified ones. In this paper, it is shown that the Cartesian product of Cayley graphs is still a Cayley graph. In illustration of this result, circulants, hypercubes, generalized hypercubes, toroidal meshes, cube-connected cycles and so on, are all Cayley graphs.
基金
国家自然科学基金资助项目 (199710 86 )
中国科学院特支费
