zbMATH — the first resource for mathematics

Locally-cyclic graphs covering complete tripartite graphs. (English) Zbl 0761.05038
A graph is locally cyclic if for each vertex the subgraph induced by its neighbors is a cycle. Such a graph has the property that every edge is in exactly two triangles. Moreover, if you place a 2-cell on each triangle the result is that the graph is embedded on a 2-dimensional manifold.
In this paper the author begins with a triangular embedding of the regular complete tripartite graph and, using a voltage assignment, derives locally-cyclic covering graphs. These graphs have the property that the number of triangles divided by the genus of the surface is asymptotically 4, and so they are extremal in this sense.

05C10 Planar graphs; geometric and topological aspects of graph theory
05C35 Extremal problems in graph theory
Full Text: EuDML
[1] BROWN M., CONNELLY R.: On graphs with a constant link: I. Directions in the Theory of Graphs. Edited by F. Harary, Academic Press, New York, 1973, pp. 19-51.
[2] CHILTON B. L., GOULD R., POLIMENI A. D.: A note on graphs whose neighbourhoods are n-cycles. Geom. Dedicata 3 (1974), 289-294. · Zbl 0325.05116
[3] GROSS J. L., TUCKER T. W.: Topological Graph Theory. Wiley-Interscience, New York, 1986.
[4] HARTSFIELD N., RINGEL G.: Clean triangulations. Combinatorica 11 (2) (1991), 145-155. · Zbl 0741.05026
[5] PARSONS T. D., PISANSKI T.: Graphs which are locally paths. Preprint Series Dept. Math. Univ. Ljubljana 26 no. 240 (1988). · Zbl 0757.05071
[6] PERKEL M.: Trivalent polygonal graphs. Congr. Numer. 45 (1984). · Zbl 0571.05016
[7] RONAN M. A.: On the second homotopy group of certain simplicial complexes and some combinatorial applications. Quart. J. Math. Oxford Ser. (2) 32 (1981), 225-233. · Zbl 0466.57004
[8] SUROWSKI D. B.: Vertex-transitive triangulations of compact orientable 2-manifolds. J. Combin. Theory Ser. B 39 (1985), 371-375. · Zbl 0578.05019
[9] VINCE A.: Locally homogeneous graphs from groups. J. Graph Theory 5 (1981), 417-422. · Zbl 0472.05055
[10] WHITE A. T.: The genus of the complete tripartite graph Kmn,n,n . J. Combin. Theory 7 (1969), 283-285. · Zbl 0186.27701
[11] WHITE A. T.: Graphs, Groups and Surfaces. North-Holland Math. Stud. 8, North-Holland, Amsterdam, 1984. · Zbl 0551.05037
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.