Akademska digitalna zbirka SLovenije - logo
E-viri
Recenzirano Odprti dostop
  • Forcing faces in plane bipa...
    Che, Zhongyuan; Chen, Zhibo

    Discrete Applied Mathematics, 01/2013, Letnik: 161, Številka: 1-2
    Journal Article

    The concept of forcing faces of a plane bipartite graph was first introduced in Che and Chen (2008) 3 Z. Che, Z. Chen, Forcing faces in plane bipartite graphs, Discrete Mathematics 308 (2008) 2427–2439, which is a natural generalization of the concept of forcing hexagons of a hexagonal system introduced in Che and Chen (2006) 2 Z. Che and Z. Chen, Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (2006) 649–668. In this paper, we further extend this concept from finite faces to all faces (including the infinite face) as follows: A face s (finite or infinite) of a 2-connected plane bipartite graph G is called a forcing face if the subgraph G−V(s) obtained by removing all vertices of s together with their incident edges has exactly one perfect matching. For a plane elementary bipartite graph G with more than two vertices, we give three necessary and sufficient conditions for G to have all faces forcing. We also give a new necessary and sufficient condition for a finite face of G to be forcing in terms of bridges in the Z-transformation graph Z(G) of G. Moreover, for the graphs G whose faces are all forcing, we obtain a characterization of forcing edges in G by using the notion of handle, from which a simple counting formula for the number of forcing edges follows.