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 Q(n)(k) denote the n-dimensional k-ary cube. This paper contributes three main results as follows: (1) qn(Q(n)(3))  = 3. (2) qn(Q(n)(k))  = 2 and 4  = 1 and k >= 9. (C) 2009 Elsevier B.V. All rights reserved.
k-ary n-cubes queue layout hypercube ternary n-cubes combinatorial problems arched leveled-planar graphs