Systems of polynomial equations are commonly used to model combinatorial problems such as independent set, graph coloring, Hamiltonian path, and others. We formulate the dominating set problem as a system of polynomial equations in two different ways: first, as a single, high-degree polynomial, and second as a collection of polynomials based on the complements of domination-critical graphs. We then provide a sufficient criterion for demonstrating that a particular ideal representation is already the universal Grobner bases of an ideal, and show that the second representation of the dominating set ideal in terms of domination-critical graphs is the universal Grobner basis for that ideal. We also present the first algebraic formulation of Vizing's conjecture, and discuss the theoretical and computational ramifications to this conjecture when using either of the two dominating set representations described above.
@article{10_37236_2194,
author = {Susan Margulies and I. V. Hicks},
title = {An algebraic exploration of dominating sets and {Vizing's} conjecture},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2194},
zbl = {1243.05188},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2194/}
}
TY - JOUR
AU - Susan Margulies
AU - I. V. Hicks
TI - An algebraic exploration of dominating sets and Vizing's conjecture
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2194/
DO - 10.37236/2194
ID - 10_37236_2194
ER -
%0 Journal Article
%A Susan Margulies
%A I. V. Hicks
%T An algebraic exploration of dominating sets and Vizing's conjecture
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2194/
%R 10.37236/2194
%F 10_37236_2194
Susan Margulies; I. V. Hicks. An algebraic exploration of dominating sets and Vizing's conjecture. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2194
