A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs (Q933668)

As recently as 1994, the maximum number of known nonisomorphic triangular imbeddings of \(K_n\) for any given \(n\), in either an orientable or a nonorientable surface, was three [\textit{S. Lawrencenko}, \textit{S. Negami} and \textit{A. T. White}, Discrete Math. 135, No.\,1--3, 367--369 (1994; Zbl 0823.05027)]. The present authors show that there exists a positive constant \(a\) and an infinite set of values of \(n\) such that the number of nonisomorphic triangular imbeddings of the complete graph \(K_n\) is at least \(n\) to the power \(an^2\). A similar result is established, for the regular complete tripartite graph \(K_{n,n,n}\). The constructions use Latin squares of side \(n\).