On the Stack Number and the Queue Number of the Bubble-Sort Graph

Yuuki TANAKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E99-A    No.6    pp.1012-1018
Publication Date: 2016/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E99.A.1012
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>>
Buy this Article

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.