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

Study on semi-paired k-disjoint path cover of unit interval graphs

作　　者：朱莉 李鹏 王爱法 ZHU Li;LI Peng;WANG Aifa(College of Science,Chongqing University of Technology,Chongqing 400054,China)

机构地区：[1]重庆理工大学理学院,重庆400054

出　　处：《山东大学学报（理学版）》2024年第2期80-90,共11页Journal of Shandong University(Natural Science)

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

摘　　要：研究单位区间图上的半配对多对多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。结果表明:图中不相交路覆盖的存在与顶点连通度和哈密顿性质密切相关。研究方法与结果为进一步研究区间图及其他相关图类的路覆盖问题提供理论依据。The fault tolerance problem of semi-paired,many to many and k-disjoint path cover(k-DPC)on unit interval graphs is studied.Using the structural characteristics of the path cover and the structural properties of the vertex order of the unit interval graphs,the unit interval graphs with semi-paired 1-DPC and k-DPC properties are characterized.At the same time,we obtain the relevant results of the unit interval graph G:for any vertex set W and any edge set F,G-W passing through F has the semi-paired 1-DPC property if and only if G is(2+r)-connected,where|W|=p,|F|=q,p+q≤r;G-W passing through F has the semi-paired k-DPC property if and only if G is(2k+r-1)-connected,where k≥2.It is shown that the existence of disjoint path covers in graphs is closely related to vertex connectivity and Hamiltonian properties.The research methods and results provide a theoretical basis for further study of the path coverage of interval graphs and other related graphs.

关 键 词：单位区间图 半配对k-DPC 容错性 路覆盖 

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