Abstract: Bubble-sort connected cycle is an important class of interconnection network.Shi Hai-zhong conjectured that BSCC(n)(n≥4) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.Denoting BSCC(n) as BSCC(n,0),we studied the new network BSCC(4,1) by using a triangle to replace per vertex of BSCC(4,0),and BSCC(4,2) was gotten by using a triangle to replace every vertex of BSCC(4,1).In the similar way,the new network was gotten by using a triangle to replace every vertex for k times.Shi Hai-zhong raised the conjecture 2 further more:BSCC(n,k) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.In this paper,we proved that BSCC(4,k) is a union of edge disjoint a Hamiltonian cycle and a perfect matching.

Key words: (n,k)-Bubble-sort connected cycle,Hamilton cycle,Conjecture,Perfect matching,Cayley graphs