Plane elementary bipartite graphs

A connected graph is called elementary if the union of all perfect matchings forms a connected subgraph. In this paper we mainly study various properties of plane elementary bipartite graphs so that many important results previously obtained for hexagonal systems are treated in a unified way. Firstly, we show that a plane bipartite graph G is elementary if and only if the boundary of each face (including the infinite face) is an alternating cycle with respect to some perfect matching of G. For a plane bipartite graph G all interior vertices of which are of the same degree, a stranger result is obtained; namely, G is elementary if and only if the boundary of the infinite face of G is an alternating cycle with respect to some perfect matching of G. Second, the concept of the Z-transformation graph Z(G) of a hexagonal system G (whose vertices represent the perfect matchings of G) is extended to a plane bipartite graph G and some results analogous to those for hexagonal systems are obtained. A peripheral face f of G is called reducible if the removal of the internal vertices and edges of the path that is the intersection of f and the exterior face of G results in a plane elementary bipartite graph. Thirdly, we obtain the reducible face decomposition for plane elementary bipartite graphs. Furthermore, sharp upper and lower bounds for the number of reducible faces are derived. Conversely, we can construct any plane elementary bipartite graphs by adding new peripheral faces one by one. As applications of this approach, we give simple construction methods for several types of plane elementary bipartite graphs G that contain a forcing edge (which belongs to exactly one perfect matching of G) and whose 2-transformation graphs Z(G) contain vertices of degree one. (C) 2000 Elsevier Science B.V. All rights reserved