The Clique In Perfect Matching Transformation Graphs Of Connected Cubic Bipartite Plane Graphs

A perfect matching of a graph G is an edge set whose edges cover all thevertices of G. As all the cubic bipartite plane graphs has at least one perfectmatching, we can form a new graph G which is called the perfect matchingtransformation graph with vertex set the perfect matchings of G, and denote itby M(G). For any two vertices of M(G) are adjacent if and only if the symmetrydiference of their corresponding perfect matchings in G are a sequence of faces.There is a special kind of connected cubic plane graphs called k-prisms, and theyare bipartite graphs when k is even. For these graphs we can find a clique oforder2|G|in the perfect matching transformation graphs of them. For a perfectmatching M of a connected cubic bipartite plane graph, if there is a face suchthat the edges in whose boundary are contained alternated in M and E\M thenthis face is called an M-alternating face. We can prove that if there is a perfectmatching M which has k M-alternating faces then there is a clique of order2k,and as for every perfect matching M it contains at least two M-alternating faces,then the perfect matching transformation graph contains a clique of order4.