A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs
type: Item
instance of: scholarly article
title: A lower bound for the number of triangular embeddings of some complete graphs and complete regular tripartite graphs
zbMATH Open document ID: 1148.05027
published in: Journal of Combinatorial Theory. Series B
publication date: 2008-07-24T00:00:00Z
review text: 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\).
reviewed by: Arthur T. White
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05B15
zbMATH DE Number: 5303719
zbMATH Keywords: Steiner triple system
zbMATH Keywords: Latin square
zbMATH Keywords: complete graph
zbMATH Keywords: triangular embedding
author: Michael John Grannell
author: T. S. Griggs
MaRDI profile type: Publication
full work available at URL: j.jctb.2007.10.002
OpenAlex ID: W1996246805
cites work: Twofold triple systems and graph imbeddings
cites work: Q5836500
cites work: Exponential families of non-isomorphic triangulations of complete graphs
cites work: Q3745851
cites work: BIEMBEDDINGS OF LATIN SQUARES AND HAMILTONIAN DECOMPOSITIONS
cites work: Recursive constructions for triangulations
cites work: Nonorientable biembeddings of Steiner triple systems
cites work: On the number of nonisomorphic orientable regular embeddings of complete graphs
cites work: Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs.
cites work: Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs
cites work: Three nonisomorphic triangulations of an orientable surface with the same complete graph
cites work: Q4773723
cites work: Q5609151
DOI: 10.1016/J.JCTB.2007.10.002
description: scientific article; zbMATH DE number 5303719