单位区间图的半配对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 / 容错性 / 路覆盖

基金资助

国家自然科学基金资助项目(11701059); 重庆市自然科学基金资助项目(cstc2020jcyj-msxmX0272); 重庆市教委科学技术研究计划项目(KJQN202001130,KJQN202101130); 重庆理工大学研究生教育高质量发展行动计划资助项目(gzlcx20222080)