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

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

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

扫码查看
原文链接
  • NETL
  • NSTL
  • 万方数据
研究单位区间图上的半配对多对多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-l)-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.

unit interval graphsemi-paired k-DPCfault tolerancepath cover

朱莉、李鹏、王爱法

展开 >

重庆理工大学理学院,重庆 400054

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

国家自然科学基金资助项目重庆市自然科学基金资助项目重庆市教委科学技术研究计划项目重庆市教委科学技术研究计划项目重庆理工大学研究生教育高质量发展行动计划资助项目

11701059cstc2020jcyjmsxmX0272KJQN202001130KJQN202101130gzlcx20222080

2024

10.6040/j.issn.1671-9352.0.2022.404

山东大学学报(理学版)
山东大学

山东大学学报(理学版)

CSTPCD北大核心
影响因子：0.437
ISSN：1671-9352
年,卷(期)：2024.59(2)
  • 24