与边控制相关的两类图

Two Classes of Graphs Related to Edge Domination

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

An edge dominating set in a graph G is a set of edges D such that every edge not in D is adjacent to an edge of D.The edge domination number of G,denoted byγ′(G),is defined as the minimum cardinality of an edge dominating set of G.We consider the effects of edge removal or addition on the edge domination number of a graph.A graph G is edge domination critical graph(edge domination minimal graph,respectively)if the addition(removal,respectively)of any edge decreasesγ′(G).In this paper we investigate various properties of these graphs.Moreover,we characterize 3-edge domination critical graphs and 3-edge domination minimal graphs.