Minimum genus embeddings of the complete graph |
| |
Authors: | Zhao Xiang Li Han Ren |
| |
Affiliation: | 1. Department of Mathematics, Minzu University of China, Beijing 100081, P. R. China;2. Department of Mathematics, East China Normal University, Shanghai 200062, P. R. China |
| |
Abstract: | In this paper, the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied. There are three approaches to solve this problem. The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths; the second approach is to find a current assignment of the current graph by the theory of current graph; the third approach is to find exponentially many embedding (or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph. According to this three approaches, we can construct exponentially many minimum genus embeddings of complete graph K 12s+8 in orientable surfaces, which show that there are at least (frac{10}{3} times (frac{200}{9})^s) distinct minimum genus embeddings for K 12s+8 in orientable surfaces. We have also proved that K 12s+8 has at least (frac{10}{3} times (frac{200}{9})^s) distinct minimum genus embeddings in non-orientable surfaces. |
| |
Keywords: | Maximum genus embedding minimum genus embedding complete graph current graph |
本文献已被 CNKI SpringerLink 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
|
点击此处可从《数学学报(英文版)》下载免费的PDF全文 |