两种特殊图类直径的上界

Upper Bounds of the Diameters of Two Classes of Graphs

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

In this paper,we study the problem about the diameter of edge domination critical graph and edge domination minimal graph. For k ≥ 3,we obtain an upper bound of the diameter of connected k- EDC graph. Furthermore,we obtain a better upper bound of the diameter of 4-EDC graph and a sharp upper bound of the diameter of 3- EDC graph. Meanwhile,we use some results of domination vertex critical graph and the relationship between the diameter of a graph G and the diameter of the line graph L（ G） of G to obtain an upper bound of the diameter of a connected k- EDM graph. Furthermore, we obtain the sharp upper bounds of the diameters of 3-EDM graph and 4-EDC graph.