A Hamiltonian Decomposition Of Three Classes Interconnection Networks

Interconnection network is an important part of super computers. When design and select a topological structure for an interconnection network, hamiltonian and fault tolerance is a significant index for evaluating the performance of network, while the conditional connectivity and the restricted connectivity offer metric parameters to measure the reliability of networks.In this paper, we consider the bubble-sort connected cycle networks and the modified bubble-sort connected cycle networks obtain the following results:1.The main results about bubble-sort connected cycle networks:In 2010, Haizhong Shi proposed a conjecture:for any integer n?4, bubble-sort connected cycles net-works is a union of a edge-disjoint hamiltonian cycles and a perfect matching.we prove the conjecture is true for n=4, n=5.2.In addition the following results are obtained.Shi Hai-zhong conjectured that BSCC(n) (n4) is an union of edge disjoint a Hamiltonian cycle and a perfect match-ing,denote BSCC(4) as BSCC(4,0), we study the new network BSCC(4,1) by using a triangle instead of per vertex of BSCC(4,0),BSCC(4,2) is getted by using a triangle replace every vertex of BSCC(4,1). In the similar way, The new network BSCC(4,k) is getted by using a triangle replace every vertex of k time. In this paper, we certify BSCC(4,k) is an union of edge disjoint a Hamiltonian cycle and a perfect matching.3.The main results about Modified bubble-sort connected cycle networks:Shi Hai-zhong raised the conjecture further more:Modified bubble-sort connected cycle networks MBSCC(n)(n?4) is an union of edge disjoint a Hamiltonian cycle and a perfect matching. (1) It is proved that the conjecture is true for n=3, n=4; (2) We decompose two cycles for n=5.