群作用图的卡氏积及其哈密尔顿圈

The Cartesian Product of Group Action Graphs and Its Hamiltonian Cycle

群作用图是一种探讨并行结构及算法设计的重要研究模型,有向连通的群作图被证明等价于一个有向Cayley图的右陪集图。本文证明群作用图的卡氏积图仍然是群作用图,由于Cayley图是群作用图的特殊情形,借助于该结论,证明了Cayley图的卡氏积仍是Cayley图。哈密尔顿圈(Hamiltonian Cycle)对于并行结构上路由方案及并行算法设计具有有重要意义,文中探讨了有向群作用的卡氏积上具有哈密尔顿圈的一个充分条件,对文献所提出的新的互连结构MDSXN(n,m,k)上Hamiltonian圈的存在性进行了理论证明。

Group Action Graph （GAG for short）has been developed for studying certain structural and algorithmic properties of the interconnection networks that underlie parallel architecture, and the connected counterpart is proven to be Cayley right coset graph. In this paper,we prove that the Cartesian product of two GAGs is still a GAG. Cayley graph is the special case of GAG,we also prove the Cartesian product of two Cayley graph is still a Cayley as a corollary of our main result. Hamiltonian cycle is very important to design routing and parallel algorithms for parallel structure. We discuss the sufficient condition for the existence of Hamiltonian cycle in the Cartesian product of GAGs if factor digraph has Hamiltonian cycle and explain that for the example MDSXN（n ,m, k）proposed in reference.