Dihedral Biembeddings and Triangulations by Complete and Complete Tripartite Graphs

摘要

We construct biembeddings of some Latin squares which are Cayley tables of dihedral groups. These facilitate the construction of n~(an2) nonisomorphic face 2-colourable triangular embeddings of the complete tripartite graph K _(n,n,n) and the complete graph K _n for linear classes of values of n and suitable constants a. Previously the best known lower bounds for the number of such embeddings that are applicable to linear classes of values of n were of the form 2~(an2). We remark that trivial upper bounds are n~(n2/3) in the case of complete graphs K _n and n~(2n2) in the case of complete tripartite graphs K _(n,n,n).