Block Graphs of \(Z\)-transformation Graphs of Perfect Matchings of Plane Elementary Bipartite Graphs

Heping Zhang1, Fuji Zhang2
1Department of Mathematics Lanzhou University Lanzhou, Gansu 730000 P. R. China
2Department of Mathematics Xiamen University Xiamen, Fujian 361005 P. R. China

Abstract

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.