边控制临界图的性质

The properties of edge domination critical graphs

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

An edge dominating set in a graph G =（ V,E） is a subset S of edges such that each edge in E／S is adjacent to at least one edge in S. The edge dominating set problem,to find an edge dominating set of minimum size,is a basic and important NP-hard problem that has been extensively studied in approximation algorithms and parameterized complexity. For a simple graph G,if the edge domination number drops whenever a new edge belonging to G-is added,then G is said to be edge domination critical graph. The property and structure of edge domination critical graphs are also studted.