单位区间图的一种刻划及其应用

给出单位区间图的一种新的刻划。并由该刻划确定出单位区间图的带宽、拓扑带宽和路色数。

单位区间图的边泛圈性

本文证明了顶点数至少为４的单位区间图是边泛圈图当且仅当它是３连通的．

关于单位区间图的二维带宽问题

二维带宽问题是将图G的顶点嵌入平面格子图,使其最长的连线尽可能短.通过引进矩形链这一概念,给出单位区间图的二维带宽精确值.

单位区间图的泛连通性

证明了顶点数至少是4的单位区间图是泛连通的当且仅当它是3-连通的。

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

研究单位区间图上的半配对多对多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。结果表明:图中不相交路覆盖的存在与顶点连通度和哈密顿性质密切相关。研究方法与结果为进一步研究区间图及其他相关图类的路覆盖问题提供理论依据。

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

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

关于n－可扩图的一些结果

本文讨论了关于ｍ－可扩图的两个极值问题；并考查了下述目类的ｎ－可扩性；正则偶图，单位区间图和分裂图。

特殊图的图修正问题研究综述

图修正问题是指在一个图中进行删除点、删除边或加边操作,使这个图转变成另一个具有某种特殊性质的图。图修正问题一直被广泛研究,尤其对弦图、区间图以及单位区间图的图修正问题的研究更是如此。弦图是完美图中最重要的一类图,也是(单位)区间图的父类图,很多经典的NP难问题在弦图上都是多项式可解的。区间图以及单位区间图在生物计算上有着广泛的应用。对这几类图的图修正问题的研究对计算机理论和实践有很大的贡献。首先介绍并总结了关于弦图、区间图以及单位区间图的图修正问题的重要算法和技术,然后对这些问题的研究现状进行分析,并提出了今后研究中值得关注的问题。

An Upper Bound for the Cubicity of Folded Hypercube

For a graph, its boxicity is the minimum dimension k such that G is representable as the intersection graph of axis-parallel boxes＇in the k-dimension space. When the boxes are restricted to be axis-parallel k-dimension cube＇s, the minimum k required to represent G is called the cubicity of G. In this paper, a special graph .called unit-interval graph. IG[X, Y] is given, then 2n such graphs which have the same vertices as V（FQn） are constructed, where FQ, is the n-dimension folded hypercube. Thanks to the specia] structure of IG[X, Y], the result that cubicity（FQn）≤ 2n is proved.