笛卡尔乘积图的k-路点覆盖

对于一个图G和一个正整数k,若图G中任意一条阶数为k的路都至少包含集合S?V(G)中的一个顶点,那么集合S就为图G的一个k-路点覆盖。最小的k-路点覆盖基数记为ψk(G),为图G的k-路点覆盖数。研究圈图分别与圈图、完全图及完全二部图做笛卡尔乘积图的k-路点覆盖,得到ψk(G)相关的精确值和上下界。

星图与二部图的某些乘积图上的k-路点覆盖

对于一个点子集S■V(G),如果图G中任意一条k路上都有至少一个点来自于S,则称集合S是图G的一个k-路点覆盖。最小的k-路点覆盖集合的阶数为图G的k-路点覆盖数,记作ψ_(k)(G)。研究了星图与二部图的笛卡尔乘积图、字典积图和直乘积图上的k-路点覆盖问题,运用枚举法以及子图的相关概念,得到了它们的最小k-路点覆盖ψ_(k)(G)值的上、下界。

单圈图的点覆盖k-路问题的有效算法

利用贪婪算法的思想,给出了一个求解树上点覆盖k-路问题的有效算法,并且进一步针对单圈图的点覆盖k-路问题,给出了一个能在多项式时间内完成的有效算法。