An algebraic exploration of dominating sets and Vizing's conjecture
type: Item
instance of: scholarly article
title: An algebraic exploration of dominating sets and Vizing's conjecture
zbMATH Open document ID: 1243.05188
author: Susan Margulies
author: Illya V. Hicks
published in: The Electronic Journal of Combinatorics
publication date: 2012-06-12T00:00:00Z
full work available at URL: v19i2p1
review text: Summary: 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 Gröbner bases of an ideal, and show that the second representation of the dominating set ideal in terms of domination-critical graphs is the universal Gröbner 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.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 13P10
zbMATH DE Number: 6045694
zbMATH Keywords: dominating sets
zbMATH Keywords: Vizing's conjecture
zbMATH Keywords: universal Gröbner bases
describes a project that uses: CoCoALib
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 6045694