zbMATH — the first resource for mathematics

Generating locally-cyclic triangulations of surfaces. (English) Zbl 0723.05053
A locally-cyclic graph is a connected graph such that for each vertex the induced subgraph on the set of its neighbors is isomorphic to a cycle. These graphs correspond uniquely to locally-cyclic triangulations of closed surfaces, that is triangulations where each cycle of length three in the underlying graph is facial.
For each closed surface \(\Sigma\), all locally-cyclic triangulations of \(\Sigma\) can be obtained from a minimal basic set B(\(\Sigma\)) by applying the vertex-splitting operation. The basis for the sphere consists of just two graphs, \(K_ 4\) (the tetrahedron) and \(O_ 3\) (the octahedron). Recently, the basis for the projective plane has been found by the second author and coauthors. For all closed surfaces, different from the two sphere, the basis may be characterized by the fact that a locally-cyclic triangulation belongs to the basis if and only if each edge in the underlying graph belongs to some 4-cycle which is homotopically non- trivial. The main result of the paper proves that for an arbitrary closed orientable surface \(\Sigma\), B(\(\Sigma\)) is finite. An application to the study of closed 2-cell embeddings of graphs in surfaces connected to the double cycle cover conjecture is presented.

05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: DOI
[1] Archdeacon, D, Densely embedded graphs, J. combin. theory ser. B, 54, 13-36, (1992) · Zbl 0694.05024
[2] Epstein, D.B.A, Curves on 2-manifolds and isotopies, Acta math., 115, 83-107, (1966) · Zbl 0136.44605
[3] Fisk, S; Mohar, B; Nedela, R, Minimal locally cyclic triangulations of the projective plane, (1990), preprint
[4] Gross, J.L; Tucker, T.W, ()
[5] Hartsfield, N; Ringel, G, Clean triangulations, Combinatorica, 12, 145-155, (1991) · Zbl 0741.05026
[6] \scA. Malnic̆, On locally cyclic graphs, preprint.
[7] Massey, W.S, ()
[8] Parsons, T.D; Pisanski, T, Graphs which are locally paths, (), 127-135, Warsaw · Zbl 0757.05071
[9] \scN. Robertson and P. D. Seymour, Graph minors X, submitted for publication.
[10] Robertson, N; Vitray, R.P, Representativity of surface embeddings, () · Zbl 0735.05032
[11] Thomassen, C, Embeddings of graphs with no short noncontractible cycles, J. combin. theory ser. B, 48, 155-177, (1990) · Zbl 0704.05011
[12] Vitray, R.P, Representativity and flexibility of drawings of graphs on the projective plane, () · Zbl 0792.05048
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.