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

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

研究单位区间图上的半配对多对多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.