%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 <i>n</i> vertices <i>G</i> by strengthening the problem of
finding maximal independent sets of <i>G</i> to the problem of finding <i>k</i>-independent
sets in <i>G</i> for<img src=\"Edit_2007ea01-dcbb-4cbb-bd75-67b681be10d8.png\" alt=\"\" /><span><span style=\"font-family:;\" \"=\"\">. It is shown that the existence of <i>k</i>-independent sets in <i>G</i> is equivalent to the existence of
solutions of a system of multivariate polynomial equations. It follows that the
problem of finding <i>k</i>-independent sets
can be realized by using Gr<span style=\"color:#636363;\">&#246;</span>bner bases of polynomial ideals. Since the number
of <i>k</i>-independent sets is finite, the
triangular equations composed by Gr&#246;bner bases are easier to be solved.
Consequently, the maximal independent sets and the independent number of <i>G</i> are obtained after solving at most <i>n</i> such equations. Finally, the numerical
example is presented to illustrate the effectiveness of this algebraic
computational method.</span></span>
%K &lt
%K i&gt
%K k&lt
%K /i&gt
%K -Independent Set
%K Maximal Independent Set
%K Gr&#246
%K bner Bases
%U http://www.scirp.org/journal/PaperInformation.aspx?PaperID=126164