两类图的导出匹配覆盖  

Cover two classes of graphs by induced matchings

作　　者：董丽[1] 汤京永[1] 秦金华[1] 

机构地区：[1]信阳师范学院数学与信息科学学院,河南信阳464000

出　　处：《宝鸡文理学院学报（自然科学版）》2007年第4期264-267,共4页Journal of Baoji University of Arts and Sciences(Natural Science Edition)

摘　　要：目的解决某些图类的导出匹配覆盖问题,特别是两条路的乘积图和非平凡树。方法采用猜想、推理、算法构造等方法进行证明。结果证明了如果图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.

关 键 词：导出匹配 导出匹配覆盖 树 

分 类 号：O157.5[理学—数学]