Improved book-embeddings of incomplete hypercubes

In this paper, we show that any incomplete hypercube with, at most, 2n+2n−1+2n−22n+2n−1+2n−2 vertices can be embedded in n−1n−1 pages for all n≥4n≥4. For the case n≥4n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2n+2n−12n+2n−1 vertices can be embedded in n−1n−1 pages for all n≥2n≥2.Besides this, we show that the result can be further improved when nn is large — e.g., any incomplete hypercube with at most 2n+2n−1+2n−2+2n−72n+2n−1+2n−2+2n−7 (respectively, 2n+2n−1+2n−2+2n−7+2n−2302n+2n−1+2n−2+2n−7+2n−230) vertices can be embedded in n−1n−1 pages for all n≥9n≥9 (respectively, n≥232n≥232).