For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On the Stack Number and the Queue Number of the Bubble-Sort Graph
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2016/06/01
Online ISSN: 1745-1337
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
bubble-sort graph, stack layout, queue layout, book embedding,
Full Text: PDF>>
In this paper, we consider the stack layout of the bubble-sort graph. The bubble-sort graph is a type of Cayley graph on a symmetric group; the bubble-sort graph has an important role for the study of Cayley graphs as interconnection networks. The stack layout and the queue layout problem that are treated in this paper have been studied widely. In this paper, we show that the stack number of the bubble-sort graph BS(n) is either n-1 or n-2. In addition, we show that an upper bound of the queue number of BS(n) is n-2.