Open Research Online - ORO

Over 40,000 publications from the broad range of OU research

Exponential families of non-isomorphic triangulations of complete graphs

Bonnington, C. P.; Grannell, M. J.; Griggs, T. S. and Siran, J. (2000). Exponential families of non-isomorphic triangulations of complete graphs. Journal of Combinatorial Theory, Series B, 78(2) pp. 169–184.

DOI: https://doi.org/10.1006/jctb.1999.1939

Abstract

We prove that the number of non-isomorphic face 2-colourable triangulations of the complete graph $K_n$ in an orientable surface is at least $2^{n^2/54 -O(n)}$ for $n$ congruent to 7 or 19 modulo 36, and is at least $2^{2n^2/81 -O(n)}$ for $n$ congruent to 19 or 55 modulo 108.