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