与边控制相关的两类图

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

两种特殊图类直径的上界

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