8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05) Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs Las Vegas, Nevada, USA December 07-December 09 ISBN: 0-7695-2509-1
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.2005.41
A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4 \le \iota \le |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 \ge 4, and also show that it is edgebipancyclic for n \ge 5. To obtain this results, we also prove that we can construct a hamiltonian cycle of Bn that contains given two nonadjacent edges. Assume that F is the subset of E(Bn). We prove that Bn - F is bipancyclic whenever n \ge 4 and |F| \le n - 3. Since Bn is a (n - 1)-regular graph, this result is optimal in the worst case.
Citation:
Yosuke Kikuchi, Toru Araki, "Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs," ispan, pp.46-51, 8th International Symposium on Parallel Architectures,Algorithms and Networks (ISPAN'05), 2005 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||