Shangwei Lin

The modified bubble-sort network is a famous Cayley graph model, which has strong symmetry and recursive structure, as well as good topological structure and properties. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we prove that for any edge subset F of the n-dimensional modified bubble-sort graph [ ], every edge of [ ] lies on a cycle of every even length from [ ] to [ ] when [ ] does not exceed [ ]. As a corollary, the cycles of every even length from 4 to [ ] can be embedded into the n-dimensional modified bubble-sort graph when the number of fault edges in the graph does not exceed [ ].

Project Euclid - mathematics and statistics online