×

Triangulations of orientable surfaces by complete tripartite graphs. (English) Zbl 1099.05025

Authors’ abstract: Orientable triangular embeddings of the complete tripartite graph \(K_{n,n,n}\) correspond to biembeddings of Latin squares. We show that if \(n\) is prime there are at least \(e^{n\ln n-n(1+ o(1))}\) nonisomorphic biembeddings of cyclic Latin squares of order \(n\). If \(n= kp\), where \(p\) is a large prime number, then the number of nonisomorphic biembeddings of cyclic Latin squares of order \(n\) is at least \(e^{p\ln p-p(1+ \ln k+ o(1))}\). Moreover, we prove that for every \(n\) there is a unique regular triangular embedding of \(K_{n,n,n}\) in an orientable surface.

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
05B15 Orthogonal arrays, Latin squares, Room squares
Full Text: DOI

References:

[1] Bonnington, C. P.; Grannell, M. J.; Griggs, T. S.; Širáň, J., Exponential families of non-isomorphic triangulations of complete graphs, J. Combin. Theory Ser. B, 78, 169-184 (2000) · Zbl 1023.05041
[2] Colbourn, C. J.; Rosa, A., Triple Systems (1999), Clarendon Press: Clarendon Press Oxford · Zbl 0607.05014
[3] Ducrocq, P. M.; Sterboul, F., Les \(G\)-systèmes triples, Ann. Discrete Math., 9, 141-145 (1980) · Zbl 0459.05034
[4] Grannell, M. J.; Griggs, T. S.; Knor, M., Biembeddings of Latin squares and Hamiltonian decompositions, Glasgow Math. J., 46, 443-457 (2004) · Zbl 1062.05030
[5] Grannell, M. J.; Griggs, T. S.; Širáň, J., Recursive constructions for triangulations, J. Graph Theory, 39, 87-107 (2002) · Zbl 0999.05021
[6] Gross, J. L.; Tucker, T. W., Topological Graph Theory (1987), Wiley: Wiley New York · Zbl 0621.05013
[7] Ringel, G., Über das Problem der Nachbargebiete auf orientierbaren Flächen, Abh. Math. Sem. Univ. Hamburg, 25, 105-127 (1961) · Zbl 0182.26603
[8] Stahl, S.; White, A., Genus embeddings for some complete tripartite graphs, Discrete Math., 9, 279-296 (1976) · Zbl 0322.05105
[9] White, A. T., Block designs and graph imbeddings, J. Combin. Theory Ser. B, 25, 166-183 (1978) · Zbl 0328.05009
[10] Youngs, J. W.T., The mystery of the Heawood conjecture, (Herris, B., Graph Theory and Its Applications (1970), Academic Press: Academic Press New York), 17-50 · Zbl 0208.52303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.