Improved book-embeddings of incomplete hypercubes |
| |
Authors: | Toru Hasunuma |
| |
Affiliation: | Department of Mathematical and Natural Sciences, The University of Tokushima, 1-1 Minamijosanjima, Tokushima 770-8502, Japan |
| |
Abstract: | In this paper, we show that any incomplete hypercube with, at most, 2n+2n−1+2n−2 vertices can be embedded in n−1 pages for all n≥4. For the case n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2n+2n−1 vertices can be embedded in n−1 pages for all n≥2.Besides this, we show that the result can be further improved when n is large — e.g., any incomplete hypercube with at most 2n+2n−1+2n−2+2n−7 (respectively, 2n+2n−1+2n−2+2n−7+2n−230) vertices can be embedded in n−1 pages for all n≥9 (respectively, n≥232). |
| |
Keywords: | Book-embedding Pagenumber Incomplete hypercube Interconnection networks |
本文献已被 ScienceDirect 等数据库收录! |
|