The Connectivity Of Z-transformation Graph Of Plane Graphs With The Applications To Forcing Spectrum Of P_m×C_n

Let G be a plane graph. Z-transformation graph Z(G) of G is defined on perfect matchings of G and two perfect matchings are adjacent if and only if they are differ only on the boundary of some interior face of G. We first prove that for a plane graph G, Z(G) is bipartite and Z(G) is connected if and only if for each nice cycle C of G, C including its interior is a plane elementary bipartite graph.Hence, the similar result for plane bipartite graph has been extended.For Pm × Cn, we prove that Z(Pm × Cn)(n ? 4) is 2-connected after deleting all vertices of degree one. Similar results have been established for Hexagonal systems[16, 17]. For the more, if n is odd and |n - m| ? 1, then no vertices of degree one; If n is odd and |n - m| = 1, then there are n vertices of degree one and we constructed all these n perfect matchings of G; If n is even, then there are 2 vertices of degree one and whose matched edges are horizontal. In the end, we prove that the total Z-transformation graph Zt(Pm × C2n)(n?2) is 2-connected.Forcing spectrum of a plane graph G is a set which contains the forcing num-ber of all perfect matchings of G. In the end, we prove that the forcing spectrum of P2m × C2n+1 is successive and also find a example of Pm×C2n whose spectrum is not successive.