A new approach to constructing exponentially many nonisomorphic nonorientable triangular embeddings of complete graphs

作者：Korzhik Vladimir P^*; Kwak Jin Ho

来源：Discrete Mathematics, 2008, 308(7): 1072-1079.

DOI：10.1016/j.disc.2007.03.060

• topological embedding
• triangular embedding
• nonisomorphic embeddings
• complete graph

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 K-n, where it = (12s + 7) (6s + 7), is at least 2(n3/2(root 2/72+o(1))). 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(alpha nl+o(nl)), l > 1, nonisomorphic nonorientable triangular embeddings of K-n for it =6t + 1, t equivalent to 2 mod 3. 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.

• 出版日期2008-4-6