边控制临界图的性质

在图G=(V,E)中,令S■E(G).如果E\S中的任一条边都与S中的至少一条边关联,则称S为图G的一个边控制集.边控制集问题,即在G中找到一个基数最小的边控制集,是一个在近似算法和参数化复杂度领域被广泛研究的基础但重要的NP-hard问题.若对于简单图G的补图中的任意一条边e,都有G+e的边控制数小于G的边控制数,则称图G是边控制临界图.主要研究了边控制临界图的性质与结构.

与边控制相关的两类图

在图G中,如果存在一个边集D,使得不在D中的每一条边都与D中的某条边关联,则称D为G的边控制集.在G的所有边控制集中,包含边数最少的称为最小边控制集,其包含的边数称为边控制数,记为γ′(G).在一个图中,我们研究了加边或去边对该图边控制数的影响.一个图称为边控制临界图(边控制极小图)如果任意增加(去除)一条边都会使边控制数下降.在本文中,我们研究了这两类图的性质,并分别刻画了3-边控制临界图和3-点控制极小图.

两种特殊图类直径的上界

对边控制临界图与边控制极小图这两种特殊图类的直径进行了研究.给出了连通的kEDC(k≥3)图的直径的一个上界,并给出了4-EDC图的直径的一个更好的上界及3-EDC图的直径的可达上界.同时,利用控制点临界图的已有的结果以及一个图的直径与其线图的直径间的关系,直接给出了连通的k-EDM图的直径的一个上界,进而给出了3-EDM图和4-EDM图的直径的可达上界.