几类互连网络的容错哈密顿性
|
摘要
将互连网络中的每个处理器抽象成一个点,把处理器之间的信道抽象成两点之间的连线,那么一个互连网络就可以抽象成一个图,称之为互联网络拓扑结构,网络的拓扑结构决定着该网络的性能.由于互联网络的拓扑结构就是图,所以图论是设计和分析互连网络的最基本且强有力的数学工具.
可嵌入性是衡量网络优劣的一个重要性能.由于用含有圈拓扑结构的图设计出来的网络通讯成本低,而且泛圈性和泛连通性也可以看成是图的哈密顿性研究的扩展,因此圈嵌入是一个重要问题.
由于网络的节点和链接都可能发生故障,所以需要研究网络的容错性,这是评估网络性能时所考虑的主要因素之一
交替群图作为计算机系统的一种互联网络拓扑结构,具有许多比超立方体和星图更好的性质,也符合网络设计高性能、低成本的原则要求.本文研究了交替群图等几类著名互联网络的容错圈嵌入、最大边连通、网络设计等问题,主要研究工作如下：
(1)研究了交替群图的容错哈密顿性和容错哈密顿连通性.对于一个n-维交替群图AGn,证明了当n≥4时,AGn是(2n-6)-容错哈密顿和(2n-6)-容错泛圈的,并且是(2n-7)-容错哈密顿连通的.本文所给的结果关于交替群图的正则度是最优的,也是对以前J.-M.Chang等人所给结果的改进.
(2)定义了匹配组合网络G=G(V1UV2,E1UE2UM),其中M是V1和V2之间的一个完全匹配.研究了G的限制连通度,G的直径的上下界与G1的直径、G2的直径和完全匹配M的关系,通过G1和G2的阶确定了几类特殊匹配组合网络G直径的上下界,最后讨论了G1和G2的泛圈性和泛连通性与G的泛圈性和泛连通性之间的关系.
(3)用凸函数的性质和数论知识研究了连通图的倒数度的上界,给出了一个连通图是最大边连通的条件,为研究超连通或超边连通图提供了新的方法,通过例子说明所给结果用于判断一个连通图是否是最大边连通图是有效的.
(4)线图方法、笛卡儿乘积方法和代数方法是互联网络设计常用的三种方法.本文用代数方法对任何含有最小元素的偏序集P,定义了其相关联零因子图G(P),证明了如果G(P)的色数X(G(P))和团数ω(G(R))是有限的,那么χ(G(P))=ω(G(P))=n+1,其中n是P的极小素理想的个数.
It is quite natural that an interconnection network may be modeled by a simple graph whose vertices represent components of the network and whose edges represent physical communica-tion links. Such a graph is called the topological structure of the interconnection network. Graph theory is a fundamental and powerful mathematical tool for designing and analyzing interconnection networks, since the topological structure of an interconnection network is a graph.
One of the essential issues in evaluating an interconnection network is to study how well other existing networks call be embedded into this network. Cycle-embedding is a central issue because networks with cycle topology are suitable for designing simple algorithms with low communication costs. Also the research of cycle-embedding in networks can be viewed as an extension of theoretical research on hamiltonicity.
In a network since vertex or edge failures may occur, it is significantly meaningful to consider fault tolerance of the network. In designing or selecting a topological structure of a interconnection network, one fundamental consideration is the fault tolerance.
The alternating group graph was proposed as an interconnection network topology for computing systems. It has many advantages over n-cubes and star graphs. Being having the two major principle-high performance and lower cost it has been intensively studied. We study the fault tolerant cycle embedding problem, the maximum-edge connectivity and the designing of a network. The main works and contributions of this dissertation are as follows:
(1) We study the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of an n-dimensional alternating group graph AGn. We give an optimal result for every n≥4:AGn is (2n-6)-fault-tolerant hamiltonian and (2n-6)-fault-tolerant pancyclic. Also it is (2n-7)-fault-tolerant hamiltonian-connected. The result we obtained is optimal on the degree of AGn. It is an improvement of a previous result given by J.-M. Chang.
(2) We define a matching composition network G=G(V1∪V2,E1∪E2∪M), in which M is a perfect matching between V1 and V2. The upper and lower bounds of the diameter of G are given. The relationship between some parameter of G and the two components is studied. Also, the pancyclicity and panconnectivity of them are analyzed.
(3) Using the properties of a convex function and numerical theory we study the inverse degree of a connected graph. Conditions for a class of graphs to be maximally edge-connected are given. Examples show the obtained result is effective.
(4) Line graphical method, cartesian product method and algebraic method are the three usually used methods to design a network. By the third method we construct a class of graphs associated to each partially ordered set P and show that if the chromatic numberχ(G(P)) and the clique numberω(G(P)) are finite, thenχ(G(P))=ω(G(P))= n+1 in which n is the number of minimal prime ideals of P.
可嵌入性是衡量网络优劣的一个重要性能.由于用含有圈拓扑结构的图设计出来的网络通讯成本低,而且泛圈性和泛连通性也可以看成是图的哈密顿性研究的扩展,因此圈嵌入是一个重要问题.
由于网络的节点和链接都可能发生故障,所以需要研究网络的容错性,这是评估网络性能时所考虑的主要因素之一
交替群图作为计算机系统的一种互联网络拓扑结构,具有许多比超立方体和星图更好的性质,也符合网络设计高性能、低成本的原则要求.本文研究了交替群图等几类著名互联网络的容错圈嵌入、最大边连通、网络设计等问题,主要研究工作如下：
(1)研究了交替群图的容错哈密顿性和容错哈密顿连通性.对于一个n-维交替群图AGn,证明了当n≥4时,AGn是(2n-6)-容错哈密顿和(2n-6)-容错泛圈的,并且是(2n-7)-容错哈密顿连通的.本文所给的结果关于交替群图的正则度是最优的,也是对以前J.-M.Chang等人所给结果的改进.
(2)定义了匹配组合网络G=G(V1UV2,E1UE2UM),其中M是V1和V2之间的一个完全匹配.研究了G的限制连通度,G的直径的上下界与G1的直径、G2的直径和完全匹配M的关系,通过G1和G2的阶确定了几类特殊匹配组合网络G直径的上下界,最后讨论了G1和G2的泛圈性和泛连通性与G的泛圈性和泛连通性之间的关系.
(3)用凸函数的性质和数论知识研究了连通图的倒数度的上界,给出了一个连通图是最大边连通的条件,为研究超连通或超边连通图提供了新的方法,通过例子说明所给结果用于判断一个连通图是否是最大边连通图是有效的.
(4)线图方法、笛卡儿乘积方法和代数方法是互联网络设计常用的三种方法.本文用代数方法对任何含有最小元素的偏序集P,定义了其相关联零因子图G(P),证明了如果G(P)的色数X(G(P))和团数ω(G(R))是有限的,那么χ(G(P))=ω(G(P))=n+1,其中n是P的极小素理想的个数.
It is quite natural that an interconnection network may be modeled by a simple graph whose vertices represent components of the network and whose edges represent physical communica-tion links. Such a graph is called the topological structure of the interconnection network. Graph theory is a fundamental and powerful mathematical tool for designing and analyzing interconnection networks, since the topological structure of an interconnection network is a graph.
One of the essential issues in evaluating an interconnection network is to study how well other existing networks call be embedded into this network. Cycle-embedding is a central issue because networks with cycle topology are suitable for designing simple algorithms with low communication costs. Also the research of cycle-embedding in networks can be viewed as an extension of theoretical research on hamiltonicity.
In a network since vertex or edge failures may occur, it is significantly meaningful to consider fault tolerance of the network. In designing or selecting a topological structure of a interconnection network, one fundamental consideration is the fault tolerance.
The alternating group graph was proposed as an interconnection network topology for computing systems. It has many advantages over n-cubes and star graphs. Being having the two major principle-high performance and lower cost it has been intensively studied. We study the fault tolerant cycle embedding problem, the maximum-edge connectivity and the designing of a network. The main works and contributions of this dissertation are as follows:
(1) We study the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity of an n-dimensional alternating group graph AGn. We give an optimal result for every n≥4:AGn is (2n-6)-fault-tolerant hamiltonian and (2n-6)-fault-tolerant pancyclic. Also it is (2n-7)-fault-tolerant hamiltonian-connected. The result we obtained is optimal on the degree of AGn. It is an improvement of a previous result given by J.-M. Chang.
(2) We define a matching composition network G=G(V1∪V2,E1∪E2∪M), in which M is a perfect matching between V1 and V2. The upper and lower bounds of the diameter of G are given. The relationship between some parameter of G and the two components is studied. Also, the pancyclicity and panconnectivity of them are analyzed.
(3) Using the properties of a convex function and numerical theory we study the inverse degree of a connected graph. Conditions for a class of graphs to be maximally edge-connected are given. Examples show the obtained result is effective.
(4) Line graphical method, cartesian product method and algebraic method are the three usually used methods to design a network. By the third method we construct a class of graphs associated to each partially ordered set P and show that if the chromatic numberχ(G(P)) and the clique numberω(G(P)) are finite, thenχ(G(P))=ω(G(P))= n+1 in which n is the number of minimal prime ideals of P.
引文
[1]Howie, J. M., Fundamentals of Semigroup Theory, Clarendon Press, Oxford,1995.
[2]Peter J. Cameron, Introduction to Algebra, Oxford University Press,1998.
[3]J. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Pub-lishers, Netherlands,2002.
[4]Kelarev, A. V., On Cayley graphs of inverse semigroups, Semigroup Forum 72 (3) (2006) 411-418.
[5]B. Steinberg, A groupoid approach to discrete inverse semigroup algebras, Advances in Mathe-matics 223 (2010) 689-727.
[6]S. Panma, U. Knauer and S. Arworn, On transitive Cayley graphs of right (left) groups and of Clifford semigroups, Thai J. Math.2 (1) (2004) 183-195.
[7]S. Panma, N. Na Chiangmai, U. Knauer and S. Arworn, Characterizations of Clifford semigroup digraphs, Discrete Math.306 (12) (2006) 1247-1252.
[8]B. Khosravi, M. Mahmoudi, On Cayley graphs of rectangular groups, Discrete Math.310 (4) (2010)804-811.
[9]J.-M. Chang, J.-S. Yang, Y.-L. Wang, Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs, Networks 44 (2004) 302-310.
[10]K. Day, A.E. Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Transactions on Parallel and Distributed Systems 8 (9) (1997) 903-907.
[11]Y. Rouskov, S. Latifi, P.K. Srimani, Conditional fault diameter of star graph networks, Journal of Parallel and Distributed Computing 33 (1) (1996) 91-97.
[12]N. Bagherzadeh, N. Nassif, S. Latifi, A routing and broadcasting scheme on faulty star graphs, IEEE Transactions on Computers 42 (11) (1993) 1398-1403.
[13]S. Latifi, E. Saberinia, X. Wu, Robustness of star graph network under link failure, Information Sciences 178 (3) (2008) 802-806.
[14]F. Harary, Conditional connectivity, Networks 13 (1983) 347-357.
[15]J.S. Fu, Conditional fault-tolerant hamiltonicity of star graphs, Parallel Computing 33 (2007) 488-496.
[16]H.S. Hung, J.S. Fu, G.H. Chen, Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Information Sciences 177 (24) (2007) 5664-5674.
[17]C.H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Com-puter Science 314 (2004) 431-443.
[18]C.H. Tsai, Y.C. Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Informa-tion Sciences 177 (24) (2007) 5590-5597.
[19]M. Wan, Z. Zhang, A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett.22 (2) (2009) 264-267.
[20]Meirun Chen and Jianguo Qian, On f-fault tolerant arc-forwarding and optical indices of all-optical folded hypercubes, Inform. Process. Lett.109 (2009) 828-831.
[21]Min Xu, Xujin Chen and Xiaodong Hu, On the restricted forwarding index problem in communi-cation networks, Mathematics with Applications,53 (2007)1633-1643.
[22]Jun Yan, Jun-Ming Xu, Chao Yang, Forwarding index of cube-connected cycles, Discrete Applied Mathematics,157 (2009) 1-7.
[23]Shangwei Lin, Shiying Wang, Super p-restricted edge connectivity of line graphs, Information Sciences,179 (2009) 3122-3126.
[24]Lutz Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett.103 (2007) 234-239.
[25]Refael Hassin, Asaf Levin, Minimum restricted diameter spanning trees, Discrete Applied Math-ematics 137 (2004) 343-357.
[26]Fang Tian, Jun-Ming Xu, Average distances and distance domination numbers, Applied Mathe-matics Letters,157 (2009) 1113-1127.
[27]Iztok Banic, Janez zerovnik, Wide diameter of Cartesian graph bundles, Discrete Mathematics 310(2010) 1697-1701.
[28]Chien-Ping Chang, Chia-Ching Wu, Conditional fault diameter of crossed cubes, Journal of Par-allel and Distributed Computing,69 (2009) 91-99.
[29]Y.-H. Teng, J.J.M. Tan, T.-Y. Ho and L.-H. Hsu, On mutually independent hamiltonian paths, Applied Mathematics Letters,19 (2006) 345-350.
[30]T.-K. Li, J.J.M. Tan and L.-H. Hsu, Hyper hamiltonian laceability on the edge fault star graph, Information Sciences 165 (2004) 59-71.
[31]C. Lin, J.J.M. Tan, H.M. Huang and L.H. Hsu, Mutually independent Hamiltonian cycles for the Pancake graphs and the star graphs, Discrete Math.309 (2009) 5474-5483.
[32]Tz-Liang Kueng, Tyne Liang, Lih-Hsing Hsu, Mutually independent hamiltonian cycles of binary wrapped butterfly graphs, Mathematical and Computer Modelling 48 (2008) 1814-1825.
[33]F.J. Paoli, W.W. Wong, and C.K. Wong, Minimum k-hamiltonian graphs Ⅱ, J. Graph Theory 10 (1986)79-95.
[34]A. Sengupta, On ring embedding in hypercubes with faulty nodes and links, Inform. Process. Lett. 68 (1998) 207-214.
[35]Y.C. Tengupt, Embedding a ring in a hypercube with both faulty links and faulty nodes, Inform. Process. Lett.59 (1996) 217-222.
[36]R.A. Rowley and B. Rose, Fault-tolerant ring embedding in de Bruijn networks, IEEE Trans Comput 42 (1993) 1480-1486.
[37]T.Y. Sung, C.Y. Lin and L.H. Hsu, Fault tolerant token ring embedding in double loop networks, Inform. Process. Lett.66 (1998) 201-207.
[38]Y.C. Tseng, S.H. Chang, and J.P. Sheu, Fault-tolerant ring embedding in a star graph with both link and node failure, IEEE Trans Parallel Distrib Syst 8 (1997) 1185-1195.
[39]C.N. Hung, L.H. Hsu, and T.Y. Sung, Christmas tree:A versatile 1-fault-tolerant design for token rings, Inform. Process. Lett.72 (1999) 55-63.
[40]C.N. Hung and S.S. Zhu, Construction for fault-tolerant hamiltonian and hamiltonian-connected graphs, Proc National Computer Symp,2001 pp. A012-A021.
[41]E. Cheng, M.J. Lipman, L. Liptak, and D. Stiebel, Hamiltonian connectivity of 2-tree-generated networks, Math Comput Model 48 (2008) 787-804.
[42]M.-C. Yang, T.-K. Li, Jimmy J.-M. Tan, L.-H. Hsu, On embedding cycles into faulty twisted cubes, Inform. Sci.176 (2006) 676-690.
[43]J. Jwo, S. Lakshmivarahan, S.K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315-326.
[44]E. Cheng, M. Lipman, Fault tolerant routing in splitstars and alternating group graphs, Congr. Numer.139 (1999) 21-32.
[45]E. Cheng, M. Lipman, Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness, Discrete Appl. Math.118 (2002) 163-179.
[46]E. Cheng, M. Lipman, H.A. Park, Super-connectivity of star graphs, alternating graphs and split stars, Ars Combin.59 (2001) 107-116.
[47]Teng, Jimmy J.-M. Tan, L.-H. Hsu, Panpositionable hamiltonicity of the alternating group graphs, Networks 50 (2007) 146-156.
[48]J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput.197 (2008) 760-767.
[49]M. Ma, J.-M. Xu, Panconnectivity of locally twisted cubes, Appl. Math. Lett.19 (2006) 673-677.
[50]T. Araki, Edge-pancyclicity of recursive circulants, Inform. Process. Lett.88 (2003) 287-292.
[51]J. Fan, X. Lin, X. Jia, Node-pancyclicity and edge-pancyclicity of crossed cubes, Inform. Process. Lett.93(2005)133-138.
[52]K.-S. Hu, S.-S. Yeoh, C. Chen, L.H. Hsu, Node-pancyclicity and edge-pancyclicity of hypercube variants, Inform. Process. Lett.102 (2007) 1-7.
[53]C.-H. Tsai, Y.-C. Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci.177 (24) (2007) 5590-5597.
[54]S.Y. Hsieh, Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges, Parallel Comput.32 (1) (2006) 84-91.
[55]M.-J. Ma, G. Liu, J.-M. Xu, Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Comput.33 (2007) 36-42.
[56]H.S. Hung, J.S. Fu, G.H. Chen, Fault-free hamiltonian cycles in crossed cubes with conditional link faults, Inform. Sci.177 (2007) 5664-5674.
[57]HC Hsu, TK Li, JJM Tan, LH Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs, IEEE Trans. Comput.53 (2004) 39-53.
[58]Andre F, Verjus J P. Hypercubes and Distributed Computers. Amsterdam, New York, Oxford: North-Halland,1989.
[59]Leighton F T. Introduction to Parallel Algorithms and Architectures:Arrays, Trees, Hypercubes. San Mateo, California:Morgan Kaufmann Publishers,1992.
[60]Efe K. A variation on the hypercube with lower diameter. IEEE Transactions on Computers,1991, 40(11):1312-1316.
[61]P. Cull, S.M. Larson, The Mobius cubes, IEEE Trans. Comput.44 (5) (1995) 647-659.
[62]P.L. Lai, J.J.M. Tan, C.H. Tsai, et al., The diagnosability of the matching composition network under the comparison diagnosis model, IEEE Trans. Computers 53 (8) (2004) 1064-1069.
[63]J. Fan, L. He, BC interconnection networks and their properties, Chinese J. Computers 26 (1) (2003) 84-90.
[64]Y.-C. Chen, C.-H. Tsai, L.-H. Hsu, J.J.M. Tan, On some super fault-tolerant hamiltonian graphs, Appl. Math. Comput.148 (2004) 729-741.
[65]Y.-C. Chen, L.-H. Hsu, J.J.M. Tan, A recursively construction scheme for super fault-tolerant hamiltonian graphs, Appl. Math. Comput.177 (2006) 465-481.
[66]J. Fan, X. Lin, The t/k-diagnosability of the BC.graphs, IEEE Trans. Comput.54 (2005) 176-184.
[67]C.D. Park, K.Y. Chwa, Hamiltonian properties on the class of hypercube networks, Inform. Pro-cess. Lett.91 (1) (2004) 11-17.
[68]J. Fan, X. Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Inform. Sci.178(2008)340-351.
[69]Y.C. Chen, J.J.M. Tan, L.H. Hsu and S.S. Kao, Super-connectivity and super-edge-connectivity for some interconnection networks, Appl. Math. Comput.140 (2003) 245-254.
[70]C. Balbuena, X. Marcote, P. Garcia-Vazquez, On restricted connectivities of permutation graphs, Networks 45 (3) (2005) 113-118.
[71]D. Bhattacharya, The minimum order of n-connected n-regular graphs with specified diameters, IEEE Trans Circuits Syst CAS-32 (1985) 407-409.
[72]Harary F, Conditional connectivity, Networks 13 (1983) 346-357.
[73]Esfahanian A H, Hakimi S L, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett.27 (1988) 195-199.
[74]Boesch F, Tindell R, Circulants and their connectivities, J. Graph Theory,8 (1984) 487-499.
[75]Angelika H, Lutz Volkmann, Maximally edge-connected and vertex-connected graphs and di-graphs:A survey, Discrete Appl. Math.308 (2008) 3265-3296.
[76]Y.Z. Tian, J.X. Meng, On super restricted edge-connectivity of edge-transitive graphs, Discrete Math.310(2010)2273-2279.
[77]C. Balbuena, J. Tang, K. Marshall and Y. Lin, Superconnectivity of regular graphs with small diameters, Discrete Appl. Math.157 (2009) 1349-1353.
[78]C. Balbuena, M. Cera, A. Dianez, P. Garcia-Vazquez and X. Marcote, On the edge-connectivity and restricted edge-connectivity of a product of graphs, Discrete Appl. Math.155 (18) (2007) 2444-2455.
[79]Xu J-M. Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht Boston London,2003.
[80]J. Plesnik, Critical graphs of given diameter, Acta Fac. Rerum Nat. Univ. Commen. Math.30 (1975)71-93.
[81]J. Plesnik, S. Znam, On equality of edge-connectivity and minimum degree of a graph, Arch. Match.25 (1989) 19-25.
[82]G. Chartrand, A graph-theoretic approach to a communications problem, SIAM J. Appl. Math. 14(1986)778-781.
[83]P. Dankelmann, L. Volkmann, New sufficient conditions for equality of minimum degree and edge-connectivity, Ars Combin.40 (1995) 270-278.
[84]J.-M. Xu, A sufficient condition for equality of arc-connectivity and minimum degree of a digraph, Discrete Math.133 (1994) 315-318.
[85]L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math.8 (1974) 351-354.
[86]S. Fajtlowicz, On conjectures of graffiti Ⅱ, Congr. Numer.60 (1987) 189-197.
[87]P. Erdos, J. Pach, J. Spencer, On the mean distance between points of a graph, Congr. Numer.64 (1988) 121-124.
[88]P. Dankelmann, H.C. Swart, P. van den Berg, Diameter and inverse degree, Discrete Math.308 (2008) 670-673.
[89]Harary F, Norman R Z, Some properties of line digraphs, Rendiconti del Circolo Matematico di Palermo.9 (1960) 161-169.
[90]Foil M A, Yebra J L A, Alegre I, Line digraph iterations and (d,k) digraph problem, IEEE Trans-actions on computers,33 (5) (1984) 400-403.
[91]Reddy S M, Kuhl J G, Hosseini S H, Lee H, On digraphs with minimum diameter and maximum connectivity, In Proceedings of the 20th Annual Allerton Conference on Communication, Cotrol and Computation, (1982) 1018-1026.
[92]Cayley A, The theory of graphs, graphical representation, Mathematical Papers, Cambridge,10 (1895)26-28.
[93]I. Beck, Coloring of a commutative ring, J. Algebra 116 (1988) 208-226.
[94]D. D. Anderson and M. Naseer, Beck's coloring of a commutative ring, J. Algebra 159 (1993) 500-514.
[95]F. R. DeMeyer, T. McKenzie and K. Schneider, The zero-divisor graph of a commutative semi-group, Semigroup Forum 65 (2002) 206-214.
[96]F. R. DeMeyer and L. DeMeyer, Zero-divisor graphs of semigroups, J. Algebra 283 (2005) 190-198.
[97]T. S. Wu, Q. Liu and L. Chen, Zero-divisor semigroups and refinements of a star graph, Discrete Math.309(2009)2510-2518.
[98]D. C. Lu and T. S. Wu, On bipartite zero-divisor graphs, Discrete Math.309 (2009) 755-762.
[99]J. D. LaGrange, Complemented zero-divisor graphs and Boolean rings, J. Algebra 315 (2007) 600-611.
[100]S. P. Redmond, On zero-divisor graphs of small finite commutative rings, Discrete Math.307 (2007)1155-1166.
[101]D. B. West, Introduction to Graph Theory, Prentice Hall,2001.
[102]B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.
[103]H. Tverberg, On Dilworth's decomposition theorem for partially ordered sets, J. Combinatorial Theory 3 (1967) 305-306.
[2]Peter J. Cameron, Introduction to Algebra, Oxford University Press,1998.
[3]J. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Pub-lishers, Netherlands,2002.
[4]Kelarev, A. V., On Cayley graphs of inverse semigroups, Semigroup Forum 72 (3) (2006) 411-418.
[5]B. Steinberg, A groupoid approach to discrete inverse semigroup algebras, Advances in Mathe-matics 223 (2010) 689-727.
[6]S. Panma, U. Knauer and S. Arworn, On transitive Cayley graphs of right (left) groups and of Clifford semigroups, Thai J. Math.2 (1) (2004) 183-195.
[7]S. Panma, N. Na Chiangmai, U. Knauer and S. Arworn, Characterizations of Clifford semigroup digraphs, Discrete Math.306 (12) (2006) 1247-1252.
[8]B. Khosravi, M. Mahmoudi, On Cayley graphs of rectangular groups, Discrete Math.310 (4) (2010)804-811.
[9]J.-M. Chang, J.-S. Yang, Y.-L. Wang, Y. Cheng, Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs, Networks 44 (2004) 302-310.
[10]K. Day, A.E. Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Transactions on Parallel and Distributed Systems 8 (9) (1997) 903-907.
[11]Y. Rouskov, S. Latifi, P.K. Srimani, Conditional fault diameter of star graph networks, Journal of Parallel and Distributed Computing 33 (1) (1996) 91-97.
[12]N. Bagherzadeh, N. Nassif, S. Latifi, A routing and broadcasting scheme on faulty star graphs, IEEE Transactions on Computers 42 (11) (1993) 1398-1403.
[13]S. Latifi, E. Saberinia, X. Wu, Robustness of star graph network under link failure, Information Sciences 178 (3) (2008) 802-806.
[14]F. Harary, Conditional connectivity, Networks 13 (1983) 347-357.
[15]J.S. Fu, Conditional fault-tolerant hamiltonicity of star graphs, Parallel Computing 33 (2007) 488-496.
[16]H.S. Hung, J.S. Fu, G.H. Chen, Fault-free Hamiltonian cycles in crossed cubes with conditional link faults, Information Sciences 177 (24) (2007) 5664-5674.
[17]C.H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Com-puter Science 314 (2004) 431-443.
[18]C.H. Tsai, Y.C. Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Informa-tion Sciences 177 (24) (2007) 5590-5597.
[19]M. Wan, Z. Zhang, A kind of conditional vertex connectivity of star graphs, Appl. Math. Lett.22 (2) (2009) 264-267.
[20]Meirun Chen and Jianguo Qian, On f-fault tolerant arc-forwarding and optical indices of all-optical folded hypercubes, Inform. Process. Lett.109 (2009) 828-831.
[21]Min Xu, Xujin Chen and Xiaodong Hu, On the restricted forwarding index problem in communi-cation networks, Mathematics with Applications,53 (2007)1633-1643.
[22]Jun Yan, Jun-Ming Xu, Chao Yang, Forwarding index of cube-connected cycles, Discrete Applied Mathematics,157 (2009) 1-7.
[23]Shangwei Lin, Shiying Wang, Super p-restricted edge connectivity of line graphs, Information Sciences,179 (2009) 3122-3126.
[24]Lutz Volkmann, Restricted arc-connectivity of digraphs, Inform. Process. Lett.103 (2007) 234-239.
[25]Refael Hassin, Asaf Levin, Minimum restricted diameter spanning trees, Discrete Applied Math-ematics 137 (2004) 343-357.
[26]Fang Tian, Jun-Ming Xu, Average distances and distance domination numbers, Applied Mathe-matics Letters,157 (2009) 1113-1127.
[27]Iztok Banic, Janez zerovnik, Wide diameter of Cartesian graph bundles, Discrete Mathematics 310(2010) 1697-1701.
[28]Chien-Ping Chang, Chia-Ching Wu, Conditional fault diameter of crossed cubes, Journal of Par-allel and Distributed Computing,69 (2009) 91-99.
[29]Y.-H. Teng, J.J.M. Tan, T.-Y. Ho and L.-H. Hsu, On mutually independent hamiltonian paths, Applied Mathematics Letters,19 (2006) 345-350.
[30]T.-K. Li, J.J.M. Tan and L.-H. Hsu, Hyper hamiltonian laceability on the edge fault star graph, Information Sciences 165 (2004) 59-71.
[31]C. Lin, J.J.M. Tan, H.M. Huang and L.H. Hsu, Mutually independent Hamiltonian cycles for the Pancake graphs and the star graphs, Discrete Math.309 (2009) 5474-5483.
[32]Tz-Liang Kueng, Tyne Liang, Lih-Hsing Hsu, Mutually independent hamiltonian cycles of binary wrapped butterfly graphs, Mathematical and Computer Modelling 48 (2008) 1814-1825.
[33]F.J. Paoli, W.W. Wong, and C.K. Wong, Minimum k-hamiltonian graphs Ⅱ, J. Graph Theory 10 (1986)79-95.
[34]A. Sengupta, On ring embedding in hypercubes with faulty nodes and links, Inform. Process. Lett. 68 (1998) 207-214.
[35]Y.C. Tengupt, Embedding a ring in a hypercube with both faulty links and faulty nodes, Inform. Process. Lett.59 (1996) 217-222.
[36]R.A. Rowley and B. Rose, Fault-tolerant ring embedding in de Bruijn networks, IEEE Trans Comput 42 (1993) 1480-1486.
[37]T.Y. Sung, C.Y. Lin and L.H. Hsu, Fault tolerant token ring embedding in double loop networks, Inform. Process. Lett.66 (1998) 201-207.
[38]Y.C. Tseng, S.H. Chang, and J.P. Sheu, Fault-tolerant ring embedding in a star graph with both link and node failure, IEEE Trans Parallel Distrib Syst 8 (1997) 1185-1195.
[39]C.N. Hung, L.H. Hsu, and T.Y. Sung, Christmas tree:A versatile 1-fault-tolerant design for token rings, Inform. Process. Lett.72 (1999) 55-63.
[40]C.N. Hung and S.S. Zhu, Construction for fault-tolerant hamiltonian and hamiltonian-connected graphs, Proc National Computer Symp,2001 pp. A012-A021.
[41]E. Cheng, M.J. Lipman, L. Liptak, and D. Stiebel, Hamiltonian connectivity of 2-tree-generated networks, Math Comput Model 48 (2008) 787-804.
[42]M.-C. Yang, T.-K. Li, Jimmy J.-M. Tan, L.-H. Hsu, On embedding cycles into faulty twisted cubes, Inform. Sci.176 (2006) 676-690.
[43]J. Jwo, S. Lakshmivarahan, S.K. Dhall, A new class of interconnection networks based on the alternating group, Networks 23 (1993) 315-326.
[44]E. Cheng, M. Lipman, Fault tolerant routing in splitstars and alternating group graphs, Congr. Numer.139 (1999) 21-32.
[45]E. Cheng, M. Lipman, Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness, Discrete Appl. Math.118 (2002) 163-179.
[46]E. Cheng, M. Lipman, H.A. Park, Super-connectivity of star graphs, alternating graphs and split stars, Ars Combin.59 (2001) 107-116.
[47]Teng, Jimmy J.-M. Tan, L.-H. Hsu, Panpositionable hamiltonicity of the alternating group graphs, Networks 50 (2007) 146-156.
[48]J.-M. Chang, J.-S. Yang, Fault-tolerant cycle-embedding in alternating group graphs, Appl. Math. Comput.197 (2008) 760-767.
[49]M. Ma, J.-M. Xu, Panconnectivity of locally twisted cubes, Appl. Math. Lett.19 (2006) 673-677.
[50]T. Araki, Edge-pancyclicity of recursive circulants, Inform. Process. Lett.88 (2003) 287-292.
[51]J. Fan, X. Lin, X. Jia, Node-pancyclicity and edge-pancyclicity of crossed cubes, Inform. Process. Lett.93(2005)133-138.
[52]K.-S. Hu, S.-S. Yeoh, C. Chen, L.H. Hsu, Node-pancyclicity and edge-pancyclicity of hypercube variants, Inform. Process. Lett.102 (2007) 1-7.
[53]C.-H. Tsai, Y.-C. Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes, Inform. Sci.177 (24) (2007) 5590-5597.
[54]S.Y. Hsieh, Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges, Parallel Comput.32 (1) (2006) 84-91.
[55]M.-J. Ma, G. Liu, J.-M. Xu, Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Comput.33 (2007) 36-42.
[56]H.S. Hung, J.S. Fu, G.H. Chen, Fault-free hamiltonian cycles in crossed cubes with conditional link faults, Inform. Sci.177 (2007) 5664-5674.
[57]HC Hsu, TK Li, JJM Tan, LH Hsu, Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs, IEEE Trans. Comput.53 (2004) 39-53.
[58]Andre F, Verjus J P. Hypercubes and Distributed Computers. Amsterdam, New York, Oxford: North-Halland,1989.
[59]Leighton F T. Introduction to Parallel Algorithms and Architectures:Arrays, Trees, Hypercubes. San Mateo, California:Morgan Kaufmann Publishers,1992.
[60]Efe K. A variation on the hypercube with lower diameter. IEEE Transactions on Computers,1991, 40(11):1312-1316.
[61]P. Cull, S.M. Larson, The Mobius cubes, IEEE Trans. Comput.44 (5) (1995) 647-659.
[62]P.L. Lai, J.J.M. Tan, C.H. Tsai, et al., The diagnosability of the matching composition network under the comparison diagnosis model, IEEE Trans. Computers 53 (8) (2004) 1064-1069.
[63]J. Fan, L. He, BC interconnection networks and their properties, Chinese J. Computers 26 (1) (2003) 84-90.
[64]Y.-C. Chen, C.-H. Tsai, L.-H. Hsu, J.J.M. Tan, On some super fault-tolerant hamiltonian graphs, Appl. Math. Comput.148 (2004) 729-741.
[65]Y.-C. Chen, L.-H. Hsu, J.J.M. Tan, A recursively construction scheme for super fault-tolerant hamiltonian graphs, Appl. Math. Comput.177 (2006) 465-481.
[66]J. Fan, X. Lin, The t/k-diagnosability of the BC.graphs, IEEE Trans. Comput.54 (2005) 176-184.
[67]C.D. Park, K.Y. Chwa, Hamiltonian properties on the class of hypercube networks, Inform. Pro-cess. Lett.91 (1) (2004) 11-17.
[68]J. Fan, X. Jia, Edge-pancyclicity and path-embeddability of bijective connection graphs, Inform. Sci.178(2008)340-351.
[69]Y.C. Chen, J.J.M. Tan, L.H. Hsu and S.S. Kao, Super-connectivity and super-edge-connectivity for some interconnection networks, Appl. Math. Comput.140 (2003) 245-254.
[70]C. Balbuena, X. Marcote, P. Garcia-Vazquez, On restricted connectivities of permutation graphs, Networks 45 (3) (2005) 113-118.
[71]D. Bhattacharya, The minimum order of n-connected n-regular graphs with specified diameters, IEEE Trans Circuits Syst CAS-32 (1985) 407-409.
[72]Harary F, Conditional connectivity, Networks 13 (1983) 346-357.
[73]Esfahanian A H, Hakimi S L, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett.27 (1988) 195-199.
[74]Boesch F, Tindell R, Circulants and their connectivities, J. Graph Theory,8 (1984) 487-499.
[75]Angelika H, Lutz Volkmann, Maximally edge-connected and vertex-connected graphs and di-graphs:A survey, Discrete Appl. Math.308 (2008) 3265-3296.
[76]Y.Z. Tian, J.X. Meng, On super restricted edge-connectivity of edge-transitive graphs, Discrete Math.310(2010)2273-2279.
[77]C. Balbuena, J. Tang, K. Marshall and Y. Lin, Superconnectivity of regular graphs with small diameters, Discrete Appl. Math.157 (2009) 1349-1353.
[78]C. Balbuena, M. Cera, A. Dianez, P. Garcia-Vazquez and X. Marcote, On the edge-connectivity and restricted edge-connectivity of a product of graphs, Discrete Appl. Math.155 (18) (2007) 2444-2455.
[79]Xu J-M. Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht Boston London,2003.
[80]J. Plesnik, Critical graphs of given diameter, Acta Fac. Rerum Nat. Univ. Commen. Math.30 (1975)71-93.
[81]J. Plesnik, S. Znam, On equality of edge-connectivity and minimum degree of a graph, Arch. Match.25 (1989) 19-25.
[82]G. Chartrand, A graph-theoretic approach to a communications problem, SIAM J. Appl. Math. 14(1986)778-781.
[83]P. Dankelmann, L. Volkmann, New sufficient conditions for equality of minimum degree and edge-connectivity, Ars Combin.40 (1995) 270-278.
[84]J.-M. Xu, A sufficient condition for equality of arc-connectivity and minimum degree of a digraph, Discrete Math.133 (1994) 315-318.
[85]L. Lesniak, Results on the edge-connectivity of graphs, Discrete Math.8 (1974) 351-354.
[86]S. Fajtlowicz, On conjectures of graffiti Ⅱ, Congr. Numer.60 (1987) 189-197.
[87]P. Erdos, J. Pach, J. Spencer, On the mean distance between points of a graph, Congr. Numer.64 (1988) 121-124.
[88]P. Dankelmann, H.C. Swart, P. van den Berg, Diameter and inverse degree, Discrete Math.308 (2008) 670-673.
[89]Harary F, Norman R Z, Some properties of line digraphs, Rendiconti del Circolo Matematico di Palermo.9 (1960) 161-169.
[90]Foil M A, Yebra J L A, Alegre I, Line digraph iterations and (d,k) digraph problem, IEEE Trans-actions on computers,33 (5) (1984) 400-403.
[91]Reddy S M, Kuhl J G, Hosseini S H, Lee H, On digraphs with minimum diameter and maximum connectivity, In Proceedings of the 20th Annual Allerton Conference on Communication, Cotrol and Computation, (1982) 1018-1026.
[92]Cayley A, The theory of graphs, graphical representation, Mathematical Papers, Cambridge,10 (1895)26-28.
[93]I. Beck, Coloring of a commutative ring, J. Algebra 116 (1988) 208-226.
[94]D. D. Anderson and M. Naseer, Beck's coloring of a commutative ring, J. Algebra 159 (1993) 500-514.
[95]F. R. DeMeyer, T. McKenzie and K. Schneider, The zero-divisor graph of a commutative semi-group, Semigroup Forum 65 (2002) 206-214.
[96]F. R. DeMeyer and L. DeMeyer, Zero-divisor graphs of semigroups, J. Algebra 283 (2005) 190-198.
[97]T. S. Wu, Q. Liu and L. Chen, Zero-divisor semigroups and refinements of a star graph, Discrete Math.309(2009)2510-2518.
[98]D. C. Lu and T. S. Wu, On bipartite zero-divisor graphs, Discrete Math.309 (2009) 755-762.
[99]J. D. LaGrange, Complemented zero-divisor graphs and Boolean rings, J. Algebra 315 (2007) 600-611.
[100]S. P. Redmond, On zero-divisor graphs of small finite commutative rings, Discrete Math.307 (2007)1155-1166.
[101]D. B. West, Introduction to Graph Theory, Prentice Hall,2001.
[102]B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.
[103]H. Tverberg, On Dilworth's decomposition theorem for partially ordered sets, J. Combinatorial Theory 3 (1967) 305-306.