Z-transformation graphs of maximum matchings of plane bipartite graphs

✍ Scribed by Heping Zhang; Rijun Zha; Haiyuan Yao

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 462 KB
• Volume: 134
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00305-6

✦ Synopsis

Let G be a plane bipartite graph. The Z-transformation graph Z(G) and its orientation Z(G) on the maximum matchings of G are deÿned. If G has a perfect matching, Z(G) and Z(G) 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 Z(G) ( Z(G)). In particular, by obtaining a result that every shortest path of Z(G) from a source of Z(G) corresponds to a directed path of Z(G), we show that every nontrivial component of Z(G) 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).