Several Applications Of Computational Algebraic Methods In Graph Theory

In Graph theory, many counting problems are usually concerned with finding maximal or minimal solutions, and most of them are solved by restricting to some specified types of graphs and using optimization methods. For a finite graph G, considering the dominating set problem, edge cover problem,strong edge coloring problem, star coloring problem and2-distance coloring problem of G, this thesis first introduces the k-counting problem,k-dominating set problem, k-edge cover problem, k-strong edge coloring problem, k-star coloring problem and k-2-distance coloring problem, and corresponding to every k-counting problem, an algebraic model is constructed in terms of systems of multivariate polynomial equations. Then, an effective criterion for the existence of the solutions to each algebraic model is reached by using the Grobner basis of polynomial ideal determined by the corresponding system of polynomial equations, and in the case that the solutions exist, the obtained Grobner basis provides a computational way for finding the solutions, and the feasibility of this method is examined by MAPLE. Finally, the obtained results are applied to give a procedure of finding maximal and minimal solutions to the corresponding problems respectively.Since the principle of computational algebra, in particular, the Grobner basis principle and method for multivariate polynomial ideals, have been very powerful in the mathematical field involving commutative multivariate polynomials, and a Grobner basis can be effectively computed by using any one of the well-developed computer algebra systems such as MAPLE, CoCoA, MACAULAY, it turns out that the work of this thesis may also provides a feasible computational way in solving other similar counting problems in graph theory.