某些容错网络的嵌入研究
摘要
互连网络拓扑结构可以用无向图G来表示,顶点集和边集V(G)和E(G)分别表示处理器和处理器之间的通信线路.互连网络结构的设计和评价中,一个重要的课题是结构嵌入问题,归结为图论问题就是图的嵌入.线性阵列和环是并行和分布式计算中最基本结构,大量应用在如图像和信号处理的实际问题中.因此研究在网络结构中有效的嵌入路和圈具有很大重要性,前人在这方面做出了大量的工作.由于网络在使用中会发生故障,对出现故障的网络的研究就很有必要,衡量一个网络的容错能力就成为了互连网络结构研究的另一个重要课题.在所有的互连网络拓扑结构中,超立方体Q_n是最受关注的.近来Bubble-sort网络,是一种Cayley图,由于有着良好的拓扑结构特性,如高对称性和递归性,继超立方体后成为我们关注的对象.
本文主要研究Bubble-sort网络和超立方体的(容错)路和圈嵌入问题,共分6章.其中第3章至第5章是主要部分.
第1章绪论主要说明研究的背景,理论意义和使用价值.
第2章介绍图和网络的基本概念,嵌入和容错的定义,Bubble-sort网络和超立方体的定义和基本性质,以及一些已有的结果.
第3章研究Bubble-sort网络的2个基本性质.
首先,我们得到Bubble-sort网络超连通度和超边连通度.
1.κ'(B_n)=2n-4,当n≥3时.λ'(B_n)=2n-4,当n≥5时.
然后我们得到Bubble-sort网络的二部分泛连通性.
2.在B_n中,当n≥5时,任意2点x,y间存在长度为l的路,其中d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).
第4章研究点容错的Bubble-sort网络最长路的嵌入问题,得到以下结果.
1.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何异色点x和y,在幸存图B_n-F_v中存在x和y之间长度为n!-2f_v-1的路.
并由此得到了点容错Bubble-sort网络中最长圈的嵌入:
2.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,在幸存图B_n-F_v中至少存在长为n!-2|F_v|的圈.
3.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何2顶点x和y同色,则在幸存图B_n-F_v中有从x到y的长为n!-2|F_v|-2的路.
在第5章中,我们主要讨论了边容错Bubble-sort网络和超立方体中的嵌入问题.
1.B_n中的故障边集F_e满足|F_e|≤n-3,B_n-F_e的每条边都包含在一个长度从6到n!的偶圈上,当n≥5时.
2.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图B_n-F_e中存在Hamilton圈.
3.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图中有长为l的偶圈,其中6≤l≤n!.
4.超立方体Q_n中的故障边集F_e满足|F_e|≤n-1,且当|F_e|=n-1时所有故障边不和一个顶点相连.当n≥4时,任意顶点uv,在幸存图中存在一条长为l的uv路,其中d(u,v)+4≤l≤2~n-1且2|(l-d(u,v)).
第6章对本文的主要工作进行了总结,对有待进一步研究的问题提出了一些看法和猜想.
附录中我们给出了证明中用到的数据.
An interconnection network is usually modeled by an undirected graph G. The sets of vertices and edges of G are denoted by V(G) and E(G), respectively represents processorsand links between processors. In interconnection networks, one of the important issues in designing and evaluating an interconnection network is to study how well other existing networks can be embedded into this network. This problem can be modeled by graph embedding problem. Linear arrays and rings (i.e. cycles) are two fundamental networks for parallel and distributed computation. Many efficient algorithms were originallydesigned based on linear arrays and rings for solving a variety of graph problems and some parallel applications, such as those in image and signal processing. Thus, it is important to have an effective path and cycle embedding in a networks. The path and cycle embedding properties of many interconnection networks have been investigated in the literature. Since faults may happen when a network is put in use, it is significantto consider faulty networks. Fault-tolerance ability is a very important issue of interconnection networks. Among all the interconnection network topologies proposed in the literature, hypercubes denoted by Q_n, is one of the most popular topologies. Very recently, bubble-sort graphs denoted by B_n, which belong to the class of Cayley graphs, have been attractive alternative to hypercubes. It has some good topological properties such as highly symmetry and recursive structure.
In this dissertation, we discuss the embedding of paths and cycles into (faulty) Bubble-sort network and hypercubes. It consists of 6 chapters, in which the 3rd chapter to the 5th chapter are main parts.
In the 1st chapter, we introduce the background of our works.
In the 2nd chapter, we first introduce terminology and notation of graph theory. Then we introduce the concepts of embedding and fault-tolerance. Furthermore, we give the definitions and some proposition of Bubble-sort networks and hypercubes. Finally, we list some known results on the topic.
In the 3rd chapter, we study basic propositions of Bubble-sort network, we first obtain the super connectivity and super edge-connectivity.
1. For n≥3,κ'(B_n) = 2n - 4. For n≥5,λ'(B_n) = 2n - 4.
Then we obtain the bipanconnectivity of Bubble-sort networks.
2. For n≥5, every pair nodes x , y in B_n, there exists a xy-path of length l with d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).
In the 4th chapter, we study the embedding of paths into Bubble-sort networks with faulty vertices. We obtain the following main results.
1. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair different colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2f_v-1.
According to the above result, we obtain:
2. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. In B_n-F_v, there exists cycle of length n!-2|F_v|.
3. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair same colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2|F_v|-2.
In the 5th chapter, we study the embedding of Bubble-sort networks and hypercubes with faulty edges. We obtain the following main results.
1. For n≥5, faulty edges set F_e of B_n with |F_e|≤n-3. Every edge of B_n-F_v, lies on even cycle of length l, 6≤l≤n!.
2. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists Hamilton cycle.
3. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists even cycle of length￡, 6≤l≤n!.
4. For n≥4, faulty edges set F_e of Q_n with |F_e|≤n-1 and not all faulty edges incident with 1 vertex, every pair nodes u, v in Q_n-F_e, there exists a uv-path of length l with d(x,y)+4≤l≤2~n-1, 2|(l-d(x,y)).
In the 6th chapter, we conclude our results and give some conjectures and problems to be studied further.
In the Appendix, we give the data used in our proof.
本文主要研究Bubble-sort网络和超立方体的(容错)路和圈嵌入问题,共分6章.其中第3章至第5章是主要部分.
第1章绪论主要说明研究的背景,理论意义和使用价值.
第2章介绍图和网络的基本概念,嵌入和容错的定义,Bubble-sort网络和超立方体的定义和基本性质,以及一些已有的结果.
第3章研究Bubble-sort网络的2个基本性质.
首先,我们得到Bubble-sort网络超连通度和超边连通度.
1.κ'(B_n)=2n-4,当n≥3时.λ'(B_n)=2n-4,当n≥5时.
然后我们得到Bubble-sort网络的二部分泛连通性.
2.在B_n中,当n≥5时,任意2点x,y间存在长度为l的路,其中d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).
第4章研究点容错的Bubble-sort网络最长路的嵌入问题,得到以下结果.
1.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何异色点x和y,在幸存图B_n-F_v中存在x和y之间长度为n!-2f_v-1的路.
并由此得到了点容错Bubble-sort网络中最长圈的嵌入:
2.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,在幸存图B_n-F_v中至少存在长为n!-2|F_v|的圈.
3.B_n中的故障点集F_v,|F_v|≤n-3.当n≥4时,任何2顶点x和y同色,则在幸存图B_n-F_v中有从x到y的长为n!-2|F_v|-2的路.
在第5章中,我们主要讨论了边容错Bubble-sort网络和超立方体中的嵌入问题.
1.B_n中的故障边集F_e满足|F_e|≤n-3,B_n-F_e的每条边都包含在一个长度从6到n!的偶圈上,当n≥5时.
2.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图B_n-F_e中存在Hamilton圈.
3.B_n中故障边集F_e满足|F_e|≤2n-7,且任意顶点都至少有2条边幸存时,当n≥4时,幸存图中有长为l的偶圈,其中6≤l≤n!.
4.超立方体Q_n中的故障边集F_e满足|F_e|≤n-1,且当|F_e|=n-1时所有故障边不和一个顶点相连.当n≥4时,任意顶点uv,在幸存图中存在一条长为l的uv路,其中d(u,v)+4≤l≤2~n-1且2|(l-d(u,v)).
第6章对本文的主要工作进行了总结,对有待进一步研究的问题提出了一些看法和猜想.
附录中我们给出了证明中用到的数据.
An interconnection network is usually modeled by an undirected graph G. The sets of vertices and edges of G are denoted by V(G) and E(G), respectively represents processorsand links between processors. In interconnection networks, one of the important issues in designing and evaluating an interconnection network is to study how well other existing networks can be embedded into this network. This problem can be modeled by graph embedding problem. Linear arrays and rings (i.e. cycles) are two fundamental networks for parallel and distributed computation. Many efficient algorithms were originallydesigned based on linear arrays and rings for solving a variety of graph problems and some parallel applications, such as those in image and signal processing. Thus, it is important to have an effective path and cycle embedding in a networks. The path and cycle embedding properties of many interconnection networks have been investigated in the literature. Since faults may happen when a network is put in use, it is significantto consider faulty networks. Fault-tolerance ability is a very important issue of interconnection networks. Among all the interconnection network topologies proposed in the literature, hypercubes denoted by Q_n, is one of the most popular topologies. Very recently, bubble-sort graphs denoted by B_n, which belong to the class of Cayley graphs, have been attractive alternative to hypercubes. It has some good topological properties such as highly symmetry and recursive structure.
In this dissertation, we discuss the embedding of paths and cycles into (faulty) Bubble-sort network and hypercubes. It consists of 6 chapters, in which the 3rd chapter to the 5th chapter are main parts.
In the 1st chapter, we introduce the background of our works.
In the 2nd chapter, we first introduce terminology and notation of graph theory. Then we introduce the concepts of embedding and fault-tolerance. Furthermore, we give the definitions and some proposition of Bubble-sort networks and hypercubes. Finally, we list some known results on the topic.
In the 3rd chapter, we study basic propositions of Bubble-sort network, we first obtain the super connectivity and super edge-connectivity.
1. For n≥3,κ'(B_n) = 2n - 4. For n≥5,λ'(B_n) = 2n - 4.
Then we obtain the bipanconnectivity of Bubble-sort networks.
2. For n≥5, every pair nodes x , y in B_n, there exists a xy-path of length l with d(x,y)+2≤l≤n!-1,2|(l-d(x,y)).
In the 4th chapter, we study the embedding of paths into Bubble-sort networks with faulty vertices. We obtain the following main results.
1. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair different colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2f_v-1.
According to the above result, we obtain:
2. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. In B_n-F_v, there exists cycle of length n!-2|F_v|.
3. For n≥4, faulty vertices set F_v of B_n with |F_v|≤n-3. Any pair same colored vertices x and y in B_n-F_v, there exists xy- path of length n!-2|F_v|-2.
In the 5th chapter, we study the embedding of Bubble-sort networks and hypercubes with faulty edges. We obtain the following main results.
1. For n≥5, faulty edges set F_e of B_n with |F_e|≤n-3. Every edge of B_n-F_v, lies on even cycle of length l, 6≤l≤n!.
2. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists Hamilton cycle.
3. For n≥4, faulty edges set F_e of B_n with |F_e|≤2n-7 and every vertex of B_n-F_e incident with at least 2 non-faulty edges, there exists even cycle of length￡, 6≤l≤n!.
4. For n≥4, faulty edges set F_e of Q_n with |F_e|≤n-1 and not all faulty edges incident with 1 vertex, every pair nodes u, v in Q_n-F_e, there exists a uv-path of length l with d(x,y)+4≤l≤2~n-1, 2|(l-d(x,y)).
In the 6th chapter, we conclude our results and give some conjectures and problems to be studied further.
In the Appendix, we give the data used in our proof.
引文
[1] Leonhard Euler, Solutio problematis ad geometriam situs pertinentis. Commetarii Academiae Scientiarum Imperialis Petropolitanae 8 (1736) 128-140.
[2] Denes K(?)nig, Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig 1936.
[3] J.-M. Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht/Boston/London 2001.
[4] J.-M. Xu, Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht/Boston/London 2003.
[5] 徐俊明,图论及其应用(第二版),合肥:中国科学技术大学出版社,2004年8月.
[6] S.Akers, B.Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transaction on Computers 38(4) (1989)555-565.
[7] S.Lakshmivarahan,J.-S.Jwo,S.Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A syrvey, Parallel Computing 19 (1993)361-407.
[8] K.Kaneko,Y.Suzuki, Node-to-Node internally disjoint paths problem in bubble-sort graph. in: Proceeding of 10th IEEE Pacific Rim International Symposium on Dependable Computing. 2004, pp. 173-182
[9] J.P.Hayes, A graph model for fault-tolerant computing systems, IEEE Transactions on Computing 25 (9)(1976)875-884.
[10] O.Ore,Hamilton connected graphs, J.Math.Pure.Aool.,42(1963),21-27
[11] J.A.Bondy, Pancyclic graphs./.J.Combin.Theory,11(1971),80-84
[12] A.Hobbs, The square of a block is vertex pancyclic, J. Combin. Theory, B20(1)(1976), 1-4
[13] B.Alspach and D.Hare,Edge-Pancyclic block-intersection graphs. Discrete Math.,97 (1-3) (1997), 17-24.
[14] Y.Alavi and J.E. Willianmson, Panconnected graphs. Studia Sci.Math. Hungar 10(1-2)(1975), 19-22.
[15] J.Mitchem and E.Schmeichel, Pancyclic and bipancyclic graphs-a survey, in Proc. First Colorado Symp. on Graphs and applications , Boulder, Co, Wiley-Interscience, New York, 1985,271-278.
[16] G.Simmons,Almost all n-dimensional rectangular lattices are Hamilton Laceable, Congr.Mimer.21(1978)103-108.
[17] S.y.Hsieh,G.h.Chen,W.Ho, Hamiltonian-laceability of star graphs, Networks 36(2000)225-232.
[18] M.Lewinter, W.Widulski, Hyper-hamilton laceable and caterpillar-spannable product graphs, Comput.Math.Appl.34(1997)99-104
[19] T.K.Li, C.H.Tsai, J.J.M Tan and L.H.Hsu, Bipanconnectivity and edgefault-tolerant bipancyclicity of hypercubes. Information Processing Letters, 87(2)(2003),107-110.
[20] M.O.Ball, Complexity of network reliability computation, Networks 10(1980),153-165.
[21] Harary,F.,Conditional connectivity.Networks, 13(1983), 346-357.
[22] Esfahanian, A. H., and Hakimi, S. L., On conputing a conditional edge-connectivity of a graph. Information Processing Letters, 27(1988), 195-199.
[23] Latifi,S,Hegde,M.,and Naraghi-Pour,M.,Conditional connectivity measures for large miltiprocessor systems. IEEE Trans. Comput. 43(2)(1994),218-221.
[24] S.Y. Hsieh, G.H. Chen, C.W. Ho, Fault-free hamiltonian cycles in faulty arrangement graphs, IEEE Transactions on Parallel and Distributed Systems 10 (3) (1999) 223-237.
[25] W.T. Huang, J.J.M. Tan, C.N. Huang L.H. Hsu, Fault-tolerant hamiltonicity of twisted cubes, Journal of Parallel and Distributed Computing 62 (2002) 591-604.
[26] M.C. Yang, T.K. Li, J.J.M. Tan, L.H. Hsu, Fault-tolerant cycle-embedding of crossed cubes, Information Processing Letters 88 (2003) 149-154.
[27] C.H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science 314 (2004) 431-443.
[28] M.Y. Chan, S. J. Lee, On the existence of hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics 4 (1991) 511-527.
[29] S.Y. Hsieh, G.H. Chen, Pancyclicity on Mobius cubes with maximal edge faults, A manuscript submitted to Networks 2003.
[30] W.T. Huang, Y. Chuang, J.J.M. Tan, L.H. Hsu, Fault-free Hamiltonian cycle in faulty M(?)bius cubes, Journal of Computing and Systems 4 (2)(2000) 106-114.
[31] 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.
[32] F. Harary, Cubical graphs and cubical dimensions, Computers and Mathematics with Applications 15 (1988) 271-275.
[33] M. Tchuente, Generation of permutations by graphical exchages. Ars Combinatoria, 14(1982),115C122.
[34] T. Araki, Y. Kikuci, Hamilton laceability of bubble-sort graphs with edge faults, Information Sciences, 177(2007)2679-2691.
[35] Y. Saad, M.H. Schultz, Topological Properties of hypercubes, IEEE Transactions on Computing 37 (7)(1988) 867-872.
[36] T.K. Li, C.H. Tsai, J.J.M. Tan, L.H. Hsu, Bipanconnected and edge-fault-tolerant bipancyclic of hypercubes, Information Processing Letters 87 (2003) 107-110.
[37] F. Harary, J.P. Hayes, Edge fault tolerance in graphs, Networks 23 (1993) 135-142.
[38] Y.R. Leu, S.Y. Kuo, Distributed fault-tolerant ring embedding and reconfiguration in hypercubes, IEEE Transactions on Computers 48 (1)(1999) 81-88.
[39] S. Latifi, S. Zheng, N. Bagherzadeh, Optimal ring embedding in hypercubes with faulty links, in Fault-Tolerant Computing, 1992. FTCS-22. Digest of Papers., Twenty-Second International Symposium on 178-184.
[40] S. Sen, A. Sengupta, S. Bandyopadhyay, On some topological properties of hypercube, incomplete hypercube and supercube, in Proc. Internal. Parallel Processing Symp. (1993) 636-642.
[41] C.H. Tsai, J.J.M. Tan, T. Liang, L.H. Hsu, Fault tolerant hamiltonian laceability of hypercubes, Information Processing Letters 83 (2002) 301-306.
[42] P.J. Yang, S.B. Tien, C.S. Raghavendra, Embedding of rings and meshes onto faulty hypercubes using free dimensions, IEEE Transactions on Computers 43 (5) (1994) 608-613.
[43] J.S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832.
[44] H. Whitney, Congruent graphs and the connectivity of graphs, American Journal of Mathematics, 54 (1932), 150-168.
[45] Y. Kikuchi and T. Araki, Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs, Information Proceeding Letters, 100 (2006), 52-59.
[46] J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults. Information Sciences. 176(2006),756-771.
[47] C.-H.Tsai and Y.-C.Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Sciences. Volume 177,Issue 24(December 2007)5590-5597.
[48] XU Jun-Ming, MA Meijie, DU Zheng-Zhong, Edge-fault-tolerant properties of hypercubes and folded hypercubes [J]. Australasian Journal of Combinatorics, 2006, 35: 7-16.
[2] Denes K(?)nig, Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig 1936.
[3] J.-M. Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht/Boston/London 2001.
[4] J.-M. Xu, Theory and Application of Graphs. Kluwer Academic Publishers, Dordrecht/Boston/London 2003.
[5] 徐俊明,图论及其应用(第二版),合肥:中国科学技术大学出版社,2004年8月.
[6] S.Akers, B.Krishnamurthy. A group-theoretic model for symmetric interconnection networks. IEEE Transaction on Computers 38(4) (1989)555-565.
[7] S.Lakshmivarahan,J.-S.Jwo,S.Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: A syrvey, Parallel Computing 19 (1993)361-407.
[8] K.Kaneko,Y.Suzuki, Node-to-Node internally disjoint paths problem in bubble-sort graph. in: Proceeding of 10th IEEE Pacific Rim International Symposium on Dependable Computing. 2004, pp. 173-182
[9] J.P.Hayes, A graph model for fault-tolerant computing systems, IEEE Transactions on Computing 25 (9)(1976)875-884.
[10] O.Ore,Hamilton connected graphs, J.Math.Pure.Aool.,42(1963),21-27
[11] J.A.Bondy, Pancyclic graphs./.J.Combin.Theory,11(1971),80-84
[12] A.Hobbs, The square of a block is vertex pancyclic, J. Combin. Theory, B20(1)(1976), 1-4
[13] B.Alspach and D.Hare,Edge-Pancyclic block-intersection graphs. Discrete Math.,97 (1-3) (1997), 17-24.
[14] Y.Alavi and J.E. Willianmson, Panconnected graphs. Studia Sci.Math. Hungar 10(1-2)(1975), 19-22.
[15] J.Mitchem and E.Schmeichel, Pancyclic and bipancyclic graphs-a survey, in Proc. First Colorado Symp. on Graphs and applications , Boulder, Co, Wiley-Interscience, New York, 1985,271-278.
[16] G.Simmons,Almost all n-dimensional rectangular lattices are Hamilton Laceable, Congr.Mimer.21(1978)103-108.
[17] S.y.Hsieh,G.h.Chen,W.Ho, Hamiltonian-laceability of star graphs, Networks 36(2000)225-232.
[18] M.Lewinter, W.Widulski, Hyper-hamilton laceable and caterpillar-spannable product graphs, Comput.Math.Appl.34(1997)99-104
[19] T.K.Li, C.H.Tsai, J.J.M Tan and L.H.Hsu, Bipanconnectivity and edgefault-tolerant bipancyclicity of hypercubes. Information Processing Letters, 87(2)(2003),107-110.
[20] M.O.Ball, Complexity of network reliability computation, Networks 10(1980),153-165.
[21] Harary,F.,Conditional connectivity.Networks, 13(1983), 346-357.
[22] Esfahanian, A. H., and Hakimi, S. L., On conputing a conditional edge-connectivity of a graph. Information Processing Letters, 27(1988), 195-199.
[23] Latifi,S,Hegde,M.,and Naraghi-Pour,M.,Conditional connectivity measures for large miltiprocessor systems. IEEE Trans. Comput. 43(2)(1994),218-221.
[24] S.Y. Hsieh, G.H. Chen, C.W. Ho, Fault-free hamiltonian cycles in faulty arrangement graphs, IEEE Transactions on Parallel and Distributed Systems 10 (3) (1999) 223-237.
[25] W.T. Huang, J.J.M. Tan, C.N. Huang L.H. Hsu, Fault-tolerant hamiltonicity of twisted cubes, Journal of Parallel and Distributed Computing 62 (2002) 591-604.
[26] M.C. Yang, T.K. Li, J.J.M. Tan, L.H. Hsu, Fault-tolerant cycle-embedding of crossed cubes, Information Processing Letters 88 (2003) 149-154.
[27] C.H. Tsai, Linear array and ring embeddings in conditional faulty hypercubes, Theoretical Computer Science 314 (2004) 431-443.
[28] M.Y. Chan, S. J. Lee, On the existence of hamiltonian circuits in faulty hypercubes, SIAM Journal on Discrete Mathematics 4 (1991) 511-527.
[29] S.Y. Hsieh, G.H. Chen, Pancyclicity on Mobius cubes with maximal edge faults, A manuscript submitted to Networks 2003.
[30] W.T. Huang, Y. Chuang, J.J.M. Tan, L.H. Hsu, Fault-free Hamiltonian cycle in faulty M(?)bius cubes, Journal of Computing and Systems 4 (2)(2000) 106-114.
[31] 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.
[32] F. Harary, Cubical graphs and cubical dimensions, Computers and Mathematics with Applications 15 (1988) 271-275.
[33] M. Tchuente, Generation of permutations by graphical exchages. Ars Combinatoria, 14(1982),115C122.
[34] T. Araki, Y. Kikuci, Hamilton laceability of bubble-sort graphs with edge faults, Information Sciences, 177(2007)2679-2691.
[35] Y. Saad, M.H. Schultz, Topological Properties of hypercubes, IEEE Transactions on Computing 37 (7)(1988) 867-872.
[36] T.K. Li, C.H. Tsai, J.J.M. Tan, L.H. Hsu, Bipanconnected and edge-fault-tolerant bipancyclic of hypercubes, Information Processing Letters 87 (2003) 107-110.
[37] F. Harary, J.P. Hayes, Edge fault tolerance in graphs, Networks 23 (1993) 135-142.
[38] Y.R. Leu, S.Y. Kuo, Distributed fault-tolerant ring embedding and reconfiguration in hypercubes, IEEE Transactions on Computers 48 (1)(1999) 81-88.
[39] S. Latifi, S. Zheng, N. Bagherzadeh, Optimal ring embedding in hypercubes with faulty links, in Fault-Tolerant Computing, 1992. FTCS-22. Digest of Papers., Twenty-Second International Symposium on 178-184.
[40] S. Sen, A. Sengupta, S. Bandyopadhyay, On some topological properties of hypercube, incomplete hypercube and supercube, in Proc. Internal. Parallel Processing Symp. (1993) 636-642.
[41] C.H. Tsai, J.J.M. Tan, T. Liang, L.H. Hsu, Fault tolerant hamiltonian laceability of hypercubes, Information Processing Letters 83 (2002) 301-306.
[42] P.J. Yang, S.B. Tien, C.S. Raghavendra, Embedding of rings and meshes onto faulty hypercubes using free dimensions, IEEE Transactions on Computers 43 (5) (1994) 608-613.
[43] J.S. Fu, Fault-tolerant cycle embedding in the hypercube, Parallel Computing 29 (2003) 821-832.
[44] H. Whitney, Congruent graphs and the connectivity of graphs, American Journal of Mathematics, 54 (1932), 150-168.
[45] Y. Kikuchi and T. Araki, Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs, Information Proceeding Letters, 100 (2006), 52-59.
[46] J.-S. Fu, Longest fault-free paths in hypercubes with vertex faults. Information Sciences. 176(2006),756-771.
[47] C.-H.Tsai and Y.-C.Lai, Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Sciences. Volume 177,Issue 24(December 2007)5590-5597.
[48] XU Jun-Ming, MA Meijie, DU Zheng-Zhong, Edge-fault-tolerant properties of hypercubes and folded hypercubes [J]. Australasian Journal of Combinatorics, 2006, 35: 7-16.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |