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

作者简介:

通讯作者:

基金项目:

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


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

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
    摘要:

    【目的】为研究不相交路径覆盖问题,在单位区间图上探讨1-不相交路径可覆盖、2-不相交路径可覆盖、k-不相交路径可覆盖在删除顶点和经过指定边后仍保持DPC性质的结构。【方法】利用单位区间图的结构特点以及路覆盖的结构性质,结合数学归纳法和反证法来研究单位区间图的配对多对多k-DPC容错性问题。【结果】单位区间图G任意删去p个点且经过q条边,仍是配对k-DPC,当且仅当G是(2k+r-1)-连通,其中(p+q)≤r。【结论】单位区间图的容错性路覆盖问题与哈密顿性质以及连通度有紧密联系。研究方法和研究结果为区间图配对k-DPC容错性问题的研究提供了理论依据,同时有助于设计在单位区间图上寻找配对k-DPC容错性的有效算法。

    Abstract:

    [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-DPC容错性问题[J].重庆师范大学学报自然科学版,2023,(2):8-17

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2023-05-22