loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
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
Yosuke Kikuchi, ERATO QCI Project, JST, Tokyo, Japan
Toru Araki, Iwate University
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.