Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs |
| |
Authors: | Yosuke Kikuchi Toru Araki |
| |
Affiliation: | a Department of Electronics and Computer Engineering, Tsuyama National College of Technology, Tsuyama, Okayama 708-8509, Japan b Department of Computer and Information Sciences, Iwate University, Morioka, Iwate 020-8551, Japan |
| |
Abstract: | A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4?l?|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the bubble-sort graph Bn is bipancyclic for n?4 and also show that it is edge-bipancyclic for n?5. Assume that F is a subset of E(Bn). We prove that Bn−F is bipancyclic, when n?4 and |F|?n−3. Since Bn is a (n−1)-regular graph, this result is optimal in the worst case. |
| |
Keywords: | Interconnection networks Bubble-sort graph Pancyclicity Edge-pancyclicity |
本文献已被 ScienceDirect 等数据库收录! |
|