Article ID Journal Published Year Pages File Type
396060 Information Sciences 2007 13 Pages PDF
Abstract

It is known that the n-dimensional bubble-sort graph Bn is bipartite, (n − 1)-regular, and has n! vertices. We first show that, for any vertex v, Bn − v has a hamiltonian path between any two vertices in the same partite set without v. Let F be a subset of edges of Bn. We next show that Bn − F has a hamiltonian path between any two vertices of different partite sets if ∣F∣ is at most n − 3. Then we also prove that Bn − F has a path of length n! − 2 between any pair of vertices in the same partite set.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
, ,