Details:
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 kindependent sets in
G for 1 ≤ k ≤ n. It is shown that the existence of kindependent sets in G is equivalent to the existence
of solutions of a system of multivariate polynomial equations. It follows that the problem of finding
kindependent sets can be realized by using Gröbner bases of polynomial ideals. Since the number of
kindependent 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  kindependent set; maximal independent set; Gröbner bases  ISSN  10053085 
Language  English  Journal  Chin. J. Eng. Math.  Volume  29  Number  5  Pages  696702  Publisher  Editorial Board of Chinese Journal of Engineering Mathematics, Faculty of Science, Xi  Year  2012  Edition  0  Translation 
No  Refereed 
No 
