Forcing faces in plane bipartite graphs (II) |
| |
Authors: | Zhongyuan Che Zhibo Chen |
| |
Affiliation: | 1. Department of Mathematics, Pennsylvania State University, Beaver Campus, Monaca, PA 15061, USA;2. Department of Mathematics, Pennsylvania State University, Greater Allegheny Campus, McKeesport, PA 15132, USA |
| |
Abstract: | 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 (finite or infinite) of a 2-connected plane bipartite graph is called a forcing face if the subgraph obtained by removing all vertices of together with their incident edges has exactly one perfect matching.For a plane elementary bipartite graph with more than two vertices, we give three necessary and sufficient conditions for to have all faces forcing. We also give a new necessary and sufficient condition for a finite face of to be forcing in terms of bridges in the -transformation graph of . Moreover, for the graphs whose faces are all forcing, we obtain a characterization of forcing edges in by using the notion of , from which a simple counting formula for the number of forcing edges follows. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|