GENERATING LOCALLY CYCLIC TRIANGULATIONS OF SURFACES

A locally cyclic graph is a connected graph such that for each vertex the induced subgraph on the set of its adjacent vertices is isomorphic to a cycle. These graphs correspond uniquely to locally cyclic triangulations of closed surfaces, i.e., triangulations where each cycle of length three in the underlying graph is facial. For each closed surface Σ, all locally cyclic triangulations of Σ can be obtained from a minimal basic set B(Σ) by applying the vertex-splitting operation. The main result proves that for an arbitrary closed orientable surface Σ, B(Σ) is finite. An application to the study of closed 2-cell embeddings of graphs in surfaces related to the double cycle cover conjecture is presented. © 1992.