Tight and untight triangulations of surfaces by complete graphs (Q1892842)

Embeddings of the complete graph \(K_n\) into surfaces is a classic topic in graph theory. This paper studies triangular embeddings of \(K_n\) into surfaces through the notion of tightness which is a natural combinatorial generalization of connectedness for graphs. The author defines a new operation among complete triangular surfaces, the coupling construction, which couples the combinatorial information of two complete triangulated surfaces with boundary of order \(n\) to produce a complete triangulated closed surface of order \(2n\) and hence yields many triangular embeddings of complete graphs into nonorientable surfaces. Applying the coupling construction, the author proves the existence of untight complete triangular embeddings and broadens the known archive of tight ones. In particular, it is shown that there exist two nonisomorphic triangular embeddings of \(K_{30}\), one tight and the other untight, in the same closed surface.