文章基本信息

标题：On the Genus of Pancake Network
本地全文：下载
作者：Quan Nguyen ; Saïd Bettayeb ‎
期刊名称：The International Arab Journal of Information Technology
印刷版ISSN：1683-3198
出版年度：2011
卷号：8
期号：3
出版社：Zarqa Private University
摘要：Both the pancake graph and star graph are Cayley graphs and are especially attractive for parallel processing. They both ‎have sublogarithmic diameter, and are fairly sparse compared to hypercubes. In this paper, we focus on another important ‎property, namely the genus. The genus of a graph is the minimum number of handles needed for drawing the graph on the ‎plane without edges crossing. We will investigate the upper bound and lower bound for the genus of pancake graph and ‎compare these values with the genus of the star graph as well as that of the hypercube.
关键词：Genus; binary hypercube; permutation; pancake network; cayley graph; and prefix reversal.‎