循环群上4度Bi-Cayley网络的研究
|
摘要
Cayley图是由有限群导出的一类重要的高对称正则图,被认为是非常合适的互连网络拓扑结构.很多优秀的互连网络如双环网,超立方体,星图都是Cayley图.大家知道对Cayley图的研究起步早并且取得非常丰富的结果,而对Bi-Cayley图的研究目前相对来说还比较少.设G是一个有限群,S是群的一组生成元(可以含G的单位元),并且能完全生成G,Bi-Cayley图是一个二部图,它的顶点集和边集分别定义为,V=G×{0,1},E=.{([g,0],[sg,1])|g∈G,s∈S}.Bi-Cayley图是Cayley图的自然推广,特别地,循环群上4度Bi-Cayley网络BC(n；±s1,±s2)是无向双环网络DLG(n；±s1,±s2)的一个自然推广.
本文的研究主要有以下三个方面1.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)连通的充分必要条件.
2.通过求得最小非负解和最小交叉解来计算循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的直径.
3.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的最优路由算法.
Cay ley graphs, which represent a category of symmetric and regular graphs derivable from finite groups, have been shown to be very suitable to serve as in-terconnection network topologies.Many outstanding networks,such as double-loop network,hybercube,star graph are Cayley graphs.We all know that the Cayley graph has been studied for a long history,and we have abundance results about it.But we have few results about Bi-Cayley still now.For a finite group G and a set of gener-ating elements S(possibly,it contains the identity element)of G,which can generate G completely, the Bi-Cayley graph BC(G,S) of G with respect to S is defined as the bipartite graph with vertex set V=G×{0,1} and edge set E={([g,0], [sg, 1])|g∈G, s∈S}.Bi-Cayley graphs are generalization of Cayley graphs.Specifically,4-degree Bi-Cayley graphs of Cyclic Groups are generalization of undirected double-loop net-works.
In this paper we maily study the following three questions.
1. The necessary and sufficient condition of the connectivity of Bi-Cayley graphs are investigated.
2. To get the smallest non-negative solution and the smallest cross solution,and use them to calculate the diameter of 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).
3.To design the arithmetic to get the shortest path of two point of connected 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).
本文的研究主要有以下三个方面1.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)连通的充分必要条件.
2.通过求得最小非负解和最小交叉解来计算循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的直径.
3.循环群上4度Bi-Cayley网络BC(n；±s1,±s2)的最优路由算法.
Cay ley graphs, which represent a category of symmetric and regular graphs derivable from finite groups, have been shown to be very suitable to serve as in-terconnection network topologies.Many outstanding networks,such as double-loop network,hybercube,star graph are Cayley graphs.We all know that the Cayley graph has been studied for a long history,and we have abundance results about it.But we have few results about Bi-Cayley still now.For a finite group G and a set of gener-ating elements S(possibly,it contains the identity element)of G,which can generate G completely, the Bi-Cayley graph BC(G,S) of G with respect to S is defined as the bipartite graph with vertex set V=G×{0,1} and edge set E={([g,0], [sg, 1])|g∈G, s∈S}.Bi-Cayley graphs are generalization of Cayley graphs.Specifically,4-degree Bi-Cayley graphs of Cyclic Groups are generalization of undirected double-loop net-works.
In this paper we maily study the following three questions.
1. The necessary and sufficient condition of the connectivity of Bi-Cayley graphs are investigated.
2. To get the smallest non-negative solution and the smallest cross solution,and use them to calculate the diameter of 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).
3.To design the arithmetic to get the shortest path of two point of connected 4-degree Bi-Cayley graphs of Cyclic Groups BC(n;±s1,±s2).
引文
[1]Akers S B, Krishnamurthy B. A group theoretic model for symmetric interconnection networks [J]. IEEE Trans on Computers,1986,34:216-223.
[2]Schibell S T, Stafford R M. Processor interconnection networks from Cayley graphs [J]. Discrete Applied Mathematics,1992,40:333-357.
[3]Annexstein F, Baumslag M, Rosenberg A. Group action graphs and par-allel architectures[J]. SIAMJ Comput,1990,19:544-569.
[4]徐俊明,徐克力.Cayley图的笛卡尔乘积.中国科技大学学报,2001,31(6)：635-640.
[5]孙雨耕,俎云霄,黄韬.群图的基本理论及置换群图的构造.天津大学学报,2000,33(2)：129-133.
[6]王爱民,孟吉翔.有限交换群上Bi-Cayley图的Hamilton性.新疆大学学报,2006,23(2)：156-158.
[7]Pathamin B.Introduction to parrallel processing algorithms and architec-tures. New York And london:Plenum Press,1999.
[8]Xu Jumming.Topological structure and analysis of interconnection net-works. Dordrecth/Boston/London:Kluwer Academic Publishers,2001.
[9]Lakshmivarahan S,Jwo JungSing,Dhall S K. Symmetry in interconnection networks Based on Cayley graphs of permutation groups:a survey.Parallel computing,1993;361-407.
[10]Bao Xing Chen, Ji Xiang Meng and Wen Jun Xiao. A constant time opti-mal routing algorithm for undirected double-loop networks. International Conference on Mobile Ad-hoc and Sensor Networks, Wuhan, China, Lec-ture Notes in Computer Science (LNCS), Springer Verlag,3794(2005), 308-316.
[11]Krishnamoorthy M S, Krishnamirthy B. Fault diameter of interconnec-tion networks [J]. Computers and Mathematics with Application,1987, 13(5/6):577-582.
[12]Hsu D F, Lyuu Y D. A graph-theoretical study of transmission delay and fault tolerance [M]. Proc. of 4th ISMM International Conference on Parallel and Distributed Computing and Systems,1991.
[13]Du D Z, Lyuu YD, Hsu D F.Line digraph iterations and connectivity analysis of de Bruijin and Kautz graphs [J]. IEEE Trans. Comput.1993, 42(5):612-616.
[14]Hsu D F, Luczak T. Note on the k-diameter of k-regular k-connected graphs [J]. Discrete Math.1994,132:291-296.
[15]Ishigami Y. The wide-diameter of the n-dimensional toroidal mesh [J]. Networks.1996,27:257-266.
[16]Li Q Sotteau D, Xu J M.2-diameter of de Bruijin graphs [J]. Networks. 1996,28:7-14.
[17]Saad Y, Schultz M H. Topological properties of hypercubes[J]. IEEE Trans. Comput.1988,37(7):867-872.
[18]孟吉翔.Cayley图的一些新结果.新疆大学学报(自然科学版).1999.(3)：10-15.
[19]陈宝兴,基于Cayley图的互连网络的研究.博士学位论文,厦门大学.
[20]Bao-Xing Chen, Wen-Jun Xiao. A Constant Time Optimal Routing Al-gorithm for Directed Double Loop Networks G(n;sl,s2).5th ACIS Inter-tional Conference on SNDP,June 30-July 2,2004,Beijing,china.
[21]B. X. Chen, J. X. Meng, W. J. Xiao. A diameter formula for an undi-rected double-loop network. Ars Combinatoria,2009,90:395-404.
[22]BaoXing CHEN,WENJUN XIAO,BEHROOZ PARHAMI. Diameter For-mulas for a Class of Undirected Double-loop Networks. Journal of Inter-connection Networks.2005.
[23]方木云,赵保华,屈玉贵,戴小平.无向双环网络G (N; r, s)直径求解方法.华中科技大学学报(自然科学报).2006,34(9)：14-17.
[24]路在平.双Cayley图的自同构群.北京大学学报(自然科学版).2003,39(1)：1-5.
[25]邹华,孟吉翔.Bi-cayley图的一些代数性质.数学学报中文版.2007,50(5)：1075-1080.
[26]陈宇,陈宝兴,谢小花.度为2的阿贝尔群上Cayley有向图的最优设计.漳州师范学院学报(自然科学版).2007,4(58)：15-20.
[27]徐尚进,靳伟,石琴,朱雁,李靖建.双Cayley图的BCI性.广西师范大学(自然科学版).2008,26(2)：33-36.
[28]祝建文,孙雨耕.置换群图路由问题研究.天津大学学报,1999,32(4)：423-426.
[29]徐俊明.组合网络理论[M].北京：科学出版社.2007.
[30]谢小花,图论中若干问题的研究,硕士论文,漳州师范学院.
[31]钟玮,陈宝兴,朱素钦.无向双环网的新的直径公式.计算机工程与应用(已录用).
[32]陈协彬.步长有限制的双环网络的最优路由算法.计算机学报,2004,27(5)：596-603
[33]刘红美.M-ary n-cube网络的最优路由.数学的实践与认识,2006,36(8)：229-233.
[34]徐荣华.由A(?),n(?)的双Cayley图构造的边传递图,硕士论文,郑州大学.
[35]徐尚进,郭松涛,刘君.双Cayley图的Hamilton性.广西大学学报：自然科学版,2009,34(2)：211-215.
[36]靳伟,双Cayley图的若干性质,硕士论文,郑州大学.
[37]邹华,孟吉翔.Bi-Cayley图的一些代数性质.数学学报中文版,2007,50(5)：1075-1080.
[38]徐俊明.计算机互连网络的最优设计.中国科学(E辑),1999,29(3)：272-278.
[39]陈协彬.步长有限制的双环网络的最优路由算法[J].计算机学报,27(2004)596-603.
[40]周建钦,汪文娟.关于最优双环网的构造[J].计算机工程与应用,2008,44(35)：62-65.
[41]徐俊明,刘琦.一类4紧优双环网无限族[J].中国科学(A),2003,33(1)：71-74.
[42]李乔,徐俊明,张忠良.最优双环网络的无限族[J].中国科学(A),1993,23(9)：979-992.
[43]林宣治,陈宝兴.关于有向双环网络L-形瓦的四个参数[J].漳州师范学院(自然科学版),2006,2：12-16.
[2]Schibell S T, Stafford R M. Processor interconnection networks from Cayley graphs [J]. Discrete Applied Mathematics,1992,40:333-357.
[3]Annexstein F, Baumslag M, Rosenberg A. Group action graphs and par-allel architectures[J]. SIAMJ Comput,1990,19:544-569.
[4]徐俊明,徐克力.Cayley图的笛卡尔乘积.中国科技大学学报,2001,31(6)：635-640.
[5]孙雨耕,俎云霄,黄韬.群图的基本理论及置换群图的构造.天津大学学报,2000,33(2)：129-133.
[6]王爱民,孟吉翔.有限交换群上Bi-Cayley图的Hamilton性.新疆大学学报,2006,23(2)：156-158.
[7]Pathamin B.Introduction to parrallel processing algorithms and architec-tures. New York And london:Plenum Press,1999.
[8]Xu Jumming.Topological structure and analysis of interconnection net-works. Dordrecth/Boston/London:Kluwer Academic Publishers,2001.
[9]Lakshmivarahan S,Jwo JungSing,Dhall S K. Symmetry in interconnection networks Based on Cayley graphs of permutation groups:a survey.Parallel computing,1993;361-407.
[10]Bao Xing Chen, Ji Xiang Meng and Wen Jun Xiao. A constant time opti-mal routing algorithm for undirected double-loop networks. International Conference on Mobile Ad-hoc and Sensor Networks, Wuhan, China, Lec-ture Notes in Computer Science (LNCS), Springer Verlag,3794(2005), 308-316.
[11]Krishnamoorthy M S, Krishnamirthy B. Fault diameter of interconnec-tion networks [J]. Computers and Mathematics with Application,1987, 13(5/6):577-582.
[12]Hsu D F, Lyuu Y D. A graph-theoretical study of transmission delay and fault tolerance [M]. Proc. of 4th ISMM International Conference on Parallel and Distributed Computing and Systems,1991.
[13]Du D Z, Lyuu YD, Hsu D F.Line digraph iterations and connectivity analysis of de Bruijin and Kautz graphs [J]. IEEE Trans. Comput.1993, 42(5):612-616.
[14]Hsu D F, Luczak T. Note on the k-diameter of k-regular k-connected graphs [J]. Discrete Math.1994,132:291-296.
[15]Ishigami Y. The wide-diameter of the n-dimensional toroidal mesh [J]. Networks.1996,27:257-266.
[16]Li Q Sotteau D, Xu J M.2-diameter of de Bruijin graphs [J]. Networks. 1996,28:7-14.
[17]Saad Y, Schultz M H. Topological properties of hypercubes[J]. IEEE Trans. Comput.1988,37(7):867-872.
[18]孟吉翔.Cayley图的一些新结果.新疆大学学报(自然科学版).1999.(3)：10-15.
[19]陈宝兴,基于Cayley图的互连网络的研究.博士学位论文,厦门大学.
[20]Bao-Xing Chen, Wen-Jun Xiao. A Constant Time Optimal Routing Al-gorithm for Directed Double Loop Networks G(n;sl,s2).5th ACIS Inter-tional Conference on SNDP,June 30-July 2,2004,Beijing,china.
[21]B. X. Chen, J. X. Meng, W. J. Xiao. A diameter formula for an undi-rected double-loop network. Ars Combinatoria,2009,90:395-404.
[22]BaoXing CHEN,WENJUN XIAO,BEHROOZ PARHAMI. Diameter For-mulas for a Class of Undirected Double-loop Networks. Journal of Inter-connection Networks.2005.
[23]方木云,赵保华,屈玉贵,戴小平.无向双环网络G (N; r, s)直径求解方法.华中科技大学学报(自然科学报).2006,34(9)：14-17.
[24]路在平.双Cayley图的自同构群.北京大学学报(自然科学版).2003,39(1)：1-5.
[25]邹华,孟吉翔.Bi-cayley图的一些代数性质.数学学报中文版.2007,50(5)：1075-1080.
[26]陈宇,陈宝兴,谢小花.度为2的阿贝尔群上Cayley有向图的最优设计.漳州师范学院学报(自然科学版).2007,4(58)：15-20.
[27]徐尚进,靳伟,石琴,朱雁,李靖建.双Cayley图的BCI性.广西师范大学(自然科学版).2008,26(2)：33-36.
[28]祝建文,孙雨耕.置换群图路由问题研究.天津大学学报,1999,32(4)：423-426.
[29]徐俊明.组合网络理论[M].北京：科学出版社.2007.
[30]谢小花,图论中若干问题的研究,硕士论文,漳州师范学院.
[31]钟玮,陈宝兴,朱素钦.无向双环网的新的直径公式.计算机工程与应用(已录用).
[32]陈协彬.步长有限制的双环网络的最优路由算法.计算机学报,2004,27(5)：596-603
[33]刘红美.M-ary n-cube网络的最优路由.数学的实践与认识,2006,36(8)：229-233.
[34]徐荣华.由A(?),n(?)的双Cayley图构造的边传递图,硕士论文,郑州大学.
[35]徐尚进,郭松涛,刘君.双Cayley图的Hamilton性.广西大学学报：自然科学版,2009,34(2)：211-215.
[36]靳伟,双Cayley图的若干性质,硕士论文,郑州大学.
[37]邹华,孟吉翔.Bi-Cayley图的一些代数性质.数学学报中文版,2007,50(5)：1075-1080.
[38]徐俊明.计算机互连网络的最优设计.中国科学(E辑),1999,29(3)：272-278.
[39]陈协彬.步长有限制的双环网络的最优路由算法[J].计算机学报,27(2004)596-603.
[40]周建钦,汪文娟.关于最优双环网的构造[J].计算机工程与应用,2008,44(35)：62-65.
[41]徐俊明,刘琦.一类4紧优双环网无限族[J].中国科学(A),2003,33(1)：71-74.
[42]李乔,徐俊明,张忠良.最优双环网络的无限族[J].中国科学(A),1993,23(9)：979-992.
[43]林宣治,陈宝兴.关于有向双环网络L-形瓦的四个参数[J].漳州师范学院(自然科学版),2006,2：12-16.