%0 Journal Article %T Solving the <i>k</i>-Independent Sets Problem of Graphs by Gröbner Bases %A Junyu Luo %A Shengzhen Ding %J Open Journal of Discrete Mathematics %P 86-94 %@ 2161-7643 %D 2023 %I Scientific Research Publishing %R 10.4236/ojdm.2023.133008 %X The aim of this paper is to given an algebraic computational method for finding maximal independent sets as well as the independent number of an arbitrary finite graph of n vertices G by strengthening the problem of finding maximal independent sets of G to the problem of finding k-independent sets in G for\"\". 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, the numerical example is presented to illustrate the effectiveness of this algebraic computational method. %K < %K i> %K k< %K /i> %K -Independent Set %K Maximal Independent Set %K Grö %K bner Bases %U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=126164