边控制临界图的性质

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