A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs |
| |
Authors: | Vladimir P Korzhik Jin Ho Kwak |
| |
Institution: | a National University of Chernivtsi, Chernivtsi 58012, Ukraine b Department of Mathematics, Pohang University of Science and Technology, San 31 Hyoja Dong, Pohang 790-784, Republic of Korea |
| |
Abstract: | We prove a theorem that for an integer s?0, if 12s+7 is a prime number, then the number of nonisomorphic face 3-colorable nonorientable triangular embeddings of Kn, where n=(12s+7)(6s+7), is at least . By some number-theoretic arguments there are an infinite number of integers s satisfying the hypothesis of the theorem. The theorem is the first known example of constructing at least 2αn?+o(n?), ?>1, nonisomorphic nonorientable triangular embeddings of Kn for n=6t+1, . To prove the theorem, we use a new approach to constructing nonisomorphic triangular embeddings of complete graphs. The approach combines a cut-and-paste technique and the index one current graph technique. A new connection between Steiner triple systems and constructing triangular embeddings of complete graphs is given. |
| |
Keywords: | Topological embedding Triangular embedding Nonisomorphic embeddings Complete graph |
本文献已被 ScienceDirect 等数据库收录! |
|