PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Jason Morton.

Title:An Algebraic Exploration of Dominating Sets and Vizing's Conjecture
Seminar:Applied Algebra Seminar
Speaker:Susan Margulies, Penn State
Abstract:
Systems of polynomial equations are commonly used to model combinatorial problems such as independent set, graph coloring, Hamiltonian path, etc.. In this talk, we formulate the dominating set problem as a system of polynomial equations, and then illustrate that the universal Grobner basis of this ideal is described by a combinatorial property directly related to dominating sets: mainly, an iteration of the complements of domination-critical graphs. We then present an algebraic formulation of Vizing's conjecture (a central question in domination theory and open since 1968), that involves the union of varieties and thus, the intersection of ideals. We conclude with a brief discussion of the computational ramifications of this formulation.

Room Reservation Information

Room Number:MB106
Date:08 / 31 / 2011
Time:02:30pm - 03:20pm