平面格子图的导出匹配数

摘要

An induced matching M in a graph G is a matching such that V(M) induces a 1-regular subgraph of G.The induced matching number of a graph G,denoted by IM(G),is the maximum number γ such that G has an induced matching of γ edges.Induced matching number of Pm × Pn is investigated in this paper.The main results are as follows:(1) If at least one of m and n is even,then IM(Pm × Pn)=[mn/4].(2) If m is odd,then IM(Pm×P3)=[3m-1/4]={3m+1/4,m≡1(mod 4),3m-1/4,m≡3(mod 4).