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

张 艳

（闽南师范大学数学与统计学院,福建漳州363000）

1 预备知识

本文考虑简单连通图.图G=(V(G),E(G)),这里集合V(G)是图G的顶点集,集合E(G)是图G的边集.H和G是两个图,如果V(H) ⊆V(G)且E(H)⊆E(G),则称H是G的子图.称不包含圈的图为无圈图或森林,称连通的无圈图为树.用Pn表示n个顶点的路,Cn表示n个顶点的圈,Tn为n个顶点的树.在完全二部图G(X,Y)中,|X|= 1 或|Y|= 1 时,称这个图为星图,用Sn表示n+ 1 个顶点的星图.若Vi⊆V,VVi表示从V中删去Vi.以V(G)的非空子集Vi为顶点集,两端点均在Vi中的全部边所组成的子图,称G由Vi导出的子图,记为G[Vi].对图G中的2 度顶点依次收缩两条与其关联的边称为该2 度顶点的双收缩,由图G连续双收缩2度顶点所得到的最小度至少为3的图称为图G的收缩核.

图G的匹配是指图G的边子集,其中任意两条边都不相邻.当匹配饱和图中所有的顶点,则称为完美匹配.匹配覆盖图是指每一条边都落在某个完美匹配中的连通图.图G的完美匹配图,记为PM(G),是以G的每个完美匹配作为顶点并且两个顶点相邻当且仅当这两点对应于G中两个完美匹配的对称差恰好是一个圈而得到的图.若PM(G)是完全图,则称G是完美匹配紧邻的(perfect matching compact),简称G是PM-紧邻的.Wang[1]已经证明图G是PM-紧邻的等价对于G中任意两个点不相交的偶圈C1和C2,G-V(C1)⋃V(C2)没有完美匹配.显然K4,K6是PM-紧邻图.对二部完全图Kp,q不相邻的顶点之间加边,然后用P3代替这些边所得到的图称为Kp,q的外剖分.若G≠K3,3且是由将K3,3的哈密尔顿圈上的一些边换为奇路得到的,则称G是K3,3的H-剖分.Wang 等[1]给出点数大于5 的哈密顿二部图若是……