图的k-支配集与Grbner基求解
Solving the algebraic model of k-dominating sets of graph by Grbner basis

摘要： 对于具有n个顶点的简单连通图G,首先证明了求解G的所有支配集等价于求解一个多元多项式方程组的所有0-1解; 其次,对于任一正整数kAbstract: Let G be a simple connected graph of n vertices. It is shown that finding all dominating sets of G is equivalent to finding all 0-1 solutions of a system of multivariate polynomial equations; furthermore, it is shown that this polynomial equation model can be modified to give a polynomial equation model for finding dominating sets of k vertices (i.e. k-dominating sets) of G, and that such a model can be solved by using the Grbner basis method. Consequently, a feasible way of finding minimal dominating sets and the dominating number of G is obtained. The numerical example is presented to illustrate the effectiveness of this algebraic computational method