zbMATH — the first resource for mathematics

Trivalent polygonal graphs. (English) Zbl 0571.05016
Combinatorics, graph theory and computing, Proc. 15th Southeast. Conf., La. State Univ. 1984, Congr. Numerantium 45, 45-70 (1984).
[For the entire collection see Zbl 0547.00011.]
In the theory of polygonal graphs, a special role seems to be played by the trivalent, strict, polygonal graphs (i.e. trivalent, connected graphs of girth \(m\geq 3\) such that every path of length 2 lies in a unique m-gon of the graph). In this paper we investigate the family of such graphs as well as a related family of triangular graphs, viz. graphs in which each vertex has an m-gon as neighborhood. We outline a number of methods, and give examples, for the construction of graphs from both families. These include using tilings of the plane (for \(m=6)\), Brown and Connelly’s construction and its generalizations (for \(m\geq 6)\), construction of polygonal graphs from groups, and examples of polygonal graphs from maps on surfaces. We also consider the question of when the duals of members from one family belong to the other family. Here dual means the following: m-gons become vertices for polygonal graphs (or triangles become vertices in the case of triangular graphs), two vertices being adjacent if and only if the corresponding m-gons (respectively, triangles) share an edge. Partial results along this line are given in the case where the polygonal graph comes from the vertices and edges of a reflexible map on an orientable surface. In a forthcoming paper (”Trivalent Polygonal Graphs of Girth 6 and 7”), the author has completely answered this duality question in the case \(m=6\).

05C10 Planar graphs; geometric and topological aspects of graph theory