两类图的导出匹配覆盖

Cover two classes of graphs by induced matchings

目的解决某些图类的导出匹配覆盖问题,特别是两条路的乘积图和非平凡树。方法采用猜想、推理、算法构造等方法进行证明。结果证明了如果图G是两条路的乘积图,则导出匹配覆盖数imc(G)∈{2,3};如果图G是一个非平凡的树,则0Δ(G)≤imc(G)≤2Δ0(G)+1,其中Δ0(G)=max{d0(u):u∈V(G)}。结论导出匹配覆盖问题的研究对于导出匹配理论的研究和应用都具有重要意义。

Aim To solve the induced matching cover problem of some graphs, such as the product of two paths and the nontrivial tree. Methods The guess, illation and construction of algorithm are used to solve the problem. Results If G is the product of two paths, the induced matching cover number imc（G）∈{2,3} ;if G is a nontrivial tree, then △0（G）≤imc（G）≤2△0（G）＋l,where △0（G）=max{d0（u）：u∈V（G）}. Conclusion The investigation of the induced matching cover problem plays a leading role in the studies of induced matching theory and its applications.