Block graphs of z-transformation graphs of perfect matchings of plane elementary bipartite graphs
Heping Zhang, FJ Zhang, 张福基 · Lanzhou University Institutional Repository · 1999
Let G be a connected plane bipartite graph. The Z-transformation graph Z(G) is a graph where the vertices are the perfect matchings of G and where two perfect matchings are joined by an edge provided their symmetric difference is the boundary of an interior face of G. For a plane elementary bipartite graph G it is shown that the block graph of Z-transformation graph Z(G) is a path. As an immediate consequence, we have that Z(G) has at most two vertices of degree one.