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

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\).