Upper bounds on the queuenumber of k-ary n-cubes

A queue layout of a graph consists of a linear order of its vertices, and a partition of its edges into queues, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph G, denoted by qn(G), is called the queuenumber of G. Heath and Rosenberg [SIAM J. Comput. 21 (1992) 927–958] showed that boolean n-cube (i.e., the n-dimensional hypercube) can be laid out using at most n−1 queues. Heath et al. [SIAM J. Discrete Math. 5 (1992) 398–412] showed that the ternary n-cube can be laid out using at most 2n−2 queues. Recently, Hasunuma and Hirota [Inform. Process. Lett. 104 (2007) 41–44] improved the upper bound on queuenumber to n−2 for hypercubes. In this paper, we deal with the upper bound on queuenumber of a wider class of graphs called k-ary n-cubes, which contains hypercubes and ternary n-cubes as subclasses. Our result improves the previous bound in the case of ternary n-cubes. Let denote the n-dimensional k-ary cube. This paper contributes three main results as follows:(1) if n⩾3.(2) if n⩾2 and 4⩽k⩽8.(3) if n⩾1 and k⩾9.