|
|||||
|
|
Upper bounds on the queuenumber of k-ary n-cubes |
|
| Authors: | Kung-Jui Pai Jou-Ming Chang |
| Affiliation: | a Department of Industrial Engineering and Management, Mingchi University of Technology, Taipei County, Taiwan, ROC b Institute of Information Science and Management, National Taipei College of Business, Taipei, Taiwan, ROC c Department of Information Management, National Taiwan University of Science and Technology, Taipei, Taiwan, ROC |
| Abstract: | 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:
|
| Keywords: | Combinatorial problems Queue layout Hypercube Ternary n-cubes k-ary n-cubes Arched leveled-planar graphs |
| 本文献已被 ScienceDirect 等数据库收录！ | |
if n?3.
if n?2 and 4?k?8.
if n?1 and k?9.