单位区间图的配对k-DPC容错性问题  

Research on Paired k-DPC Fault Tolerance of Unit Interval Graphs

作　　者：李鹏 朱莉 王爱法 尚建辉 LI Peng;ZHU Li;WANG Aifa;SHANG Jianhui(College of Science,Chongqing University of Technology,Chongqing 400054;School of Mathematical Sciences,Shanghai Jiaotong University,Shanghai 200240,China)

机构地区：[1]重庆理工大学理学院,重庆400054 [2]上海交通大学数学科学学院,上海200240

出　　处：《重庆师范大学学报（自然科学版）》2023年第2期8-17,共10页Journal of Chongqing Normal University:Natural Science

基　　金：国家自然科学基金项目(No.11701059);重庆市自然科学基金项目(No.cstc2020jcyj-msxmX0272);重庆市教育委员会科学技术研究计划项目(No.KJQN202001130;No.KJQN202101130;No.KJQN202001107);上海自然科学基金项目(No.20ZR1427200);重庆理工大学研究生教育高质量发展行动计划(No.gzlcx20222080)。

摘　　要：[目的]为研究不相交路径覆盖问题,在单位区间图上探讨1-不相交路径可覆盖、2-不相交路径可覆盖、k-不相交路径可覆盖在删除顶点和经过指定边后仍保持DPC性质的结构。[方法]利用单位区间图的结构特点以及路覆盖的结构性质,结合数学归纳法和反证法来研究单位区间图的配对多对多k-DPC容错性问题。[结果]单位区间图G任意删去p个点且经过q条边,仍是配对k-DPC,当且仅当G是(2k+r-1)-连通,其中(p+q)≤r。[结论]单位区间图的容错性路覆盖问题与哈密顿性质以及连通度有紧密联系。研究方法和研究结果为区间图配对k-DPC容错性问题的研究提供了理论依据,同时有助于设计在单位区间图上寻找配对k-DPC容错性的有效算法。[Purposes]In order to study the disjoint path cover(DPC for short)problem,the structures of 1-disjoint path coverable,2-disjoint path coverable and k-disjoint path coverable that still maintain the DPC property after deleting vertices and passing through specified edges are discussed on the unit interval graph.[Methods]Using the structural characteristics of unit interval graphs and the structural properties of path cover,the paired many to many k-DPC fault tolerance problem of unit interval graphs is studied by mathematical induction and counter proof method.[Findings]Arbitrarily delete p vertices and pass through q edges,the unit interval graph G is still paired k-DPC,if and only if G is(2k+r-1)-connected,where(p+q)≤r.[Conclusions]The fault tolerance path cover problem of unit interval graphs is closely related to Hamiltonian properties and connectivity.The research results and methods provide a theoretical basis for the research of paired k-DPC fault tolerance of interval graphs,and help to design an effective algorithm to find paired k-DPC fault tolerance on unit interval graphs.

关 键 词：路覆盖 配对k-不相交路径可覆盖 单位区间图 容错性 

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