Z-transformation graphs of maximum matchings of plane bipartite graphs ?
Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation on the maximum matchings of G are defined. If G has a perfect matching, Z(G) and are the usual Z-transformation graph and digraph. If G has neither isolated vertices nor perfect matching, then Z(G) is not connected. This paper mainly shows that some basic results for Z-transformation graph (digraph) of a plane elementary bipartite graph still hold for every nontrivial component of . In particular, by obtaining a result that every shortest path of Z(G) from a source of corresponds to a directed path of , we show that every nontrivial component of has exactly one source and one sink. Accordingly, it follows that the block graph of every nontrivial component of Z(G) is a path. In addition, we give a simple characterization for a maximum matching of G being a cut-vertex of Z(G).
z-transformation graph maximum matching plane bipartite graph perfect matching