Show simple item record

dc.contributor.authorMargulies, S.
Hicks, I.V.
dc.date.accessioned 2013-07-12T20:04:53Z
dc.date.available 2013-07-12T20:04:53Z
dc.date.issued 2012
dc.identifier.citation Margulies, S. and Hicks, I.V.. "An Algebraic Exploration of Dominating Sets and Vizing's Conjecture." The Electronic Journal of Combinatorics, 19, no. 2 (2012) The Electronic Journal of Combinatorics: https://hdl.handle.net/1911/71548.
dc.identifier.urihttps://hdl.handle.net/1911/71548
dc.description.abstract 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 di erent ways: rst, 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 su cient criterion for demonstrating that a particular ideal representation is already the universal Gr obner 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 obner basis for that ideal. We also present the rst algebraic formulation of Vizing's conjecture, and discuss the theoretical and computational rami cations to this conjecture when using either of the two dominating set representations described above.
dc.language.iso eng
dc.publisher The Electronic Journal of Combinatorics
dc.rights Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use.
dc.title An Algebraic Exploration of Dominating Sets and Vizing's Conjecture
dc.type Journal article
dc.contributor.funder National Science Foundation
dc.contributor.funder Rice University
dc.citation.journalTitle The Electronic Journal of Combinatorics
dc.subject.keyworddominating sets
Vizing's conjecture
universal Grobner bases
dc.citation.volumeNumber 19
dc.citation.issueNumber 2
dc.embargo.terms none
dc.type.dcmi Text
dc.identifier.grantID DMS-0729251 (National Science Foundation)
dc.identifier.grantID CMMI-0926618 (National Science Foundation)
dc.identifier.grantID DMS-0240058 (National Science Foundation)
dc.identifier.grantID VIGRE program (Rice University)
dc.type.publication publisher version


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record