单位区间图的半配对k-不相交路覆盖研究

摘要

研究单位区间图上的半配对多对多k-不相交路覆盖(k-disjoint path cover,k-DPC)的容错性问题，利用路覆盖的结构特点，结合单位区间图顶点序的结构性质，刻画具有半配对1-DPC和k-DPC性质的单位区间图。同时得到单位区间图G任意删去点集W且任意经过边集F的相关结果：G-W且经过F具有半配对1-DPC性质当且仅当G是(2+r)-连通，其中|W|=p,|F|=q,p+q≤r;G-W且经过F具有半配对k-DPC性质当且仅当G是(2k+r-1)-连通，其中k≥2。结果表明：图中不相交路覆盖的存在与顶点连通度和哈密顿性质密切相关。研究方法与结果为进一步研究区间图及其他相关图类的路覆盖问题提供理论依据。

关键词

单位区间图 / 半配对k-DPC / 容错性 / 路覆盖