一类笛卡儿乘积图的PM-紧邻性质

PM-compact property of a class of cartesian product graphs

图G的完美匹配图,记为PM(G),是以G的每个完美匹配作为顶点并且两个顶点相邻当且仅当这两点对应于G中两个完美匹配的对称差恰好是一个圈而得到的图.若PM(G)是完全图,则称G是完美匹配紧邻的,简称G是PM-紧邻的.研究了一类笛卡儿乘积图的PM-紧邻性质,完全刻画在这类笛卡儿乘积图中所有的PM-紧邻图.

The perfect matching graph of a graph G,denoted by PM(G),is the graph gotten by letting each perfect matching of G be a vertex of PM(G),and two vertices in PM(G)are adjacent if and only if the symmetric difference of those two perfect matchings of G is a cycle.If PM(G)is a complete graph,then we call G is perfect matching compact,or PM-compact for short.We study PM-compact property of a class of the cartesian product graphs in this paper.All PM-compact graphs in the class of cartesian product graphs are characterized.