|Title||Solving the $k$-independent sets problem of graphs by Gr\"obner bases.|
|Author(s)|| Xuewei Xiong, Zhonghua Zhao|
|Type||Article in Journal|
|Abstract||The aim of this paper is to given an algebraic computational method for finding maximal inde-|
pendent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthen-
ing the problem of finding maximal independent sets of G to the problem of finding k-independent sets in
G for 1 ≤ k ≤ n. It is shown that the existence of k-independent sets in G is equivalent to the existence
of solutions of a system of multivariate polynomial equations. It follows that the problem of finding
k-independent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of
k-independent sets is finite, the triangular equations composed by Gröbner bases are easier to be solved.
Consequently, the maximal independent sets and the independent number of G are obtained after solving
at most n such equations. Finally, a numerical example is presented to illustrated the effectiveness of
this algebraic computational method.
|Keywords||k-independent set; maximal independent set; Gröbner bases|
|Journal||Chin. J. Eng. Math.|
|Publisher||Editorial Board of Chinese Journal of Engineering Mathematics, Faculty of Science, Xi|