Trivial Results using Complicated Methods

In 1968 Vizing conjectured that the product of the domination number of two graphs is always smaller or equal to the domination number of the product graph. Today, we still don't know whether this conjecture is true or not.

In this talk we will investigate a completely new way of tackling Vizing's conjecture. First we will build an algebraic model of the conjecture with some parameters. Then we will translate Vizing's conjecture for these parameters into the question of whether a specific polynomial is nonnegative over a specific ideal. Then we will do another reformulation to the question of whether a specific polynomial is a sum-of-squares polynomial on a certain level of the sos-hierarchy and discuss how we can use semidefinite programming to answer these kind of questions.

 We obtain results on graphs, for which the combinatorics is fairly trivial. But we provide a proof of concept of our new method to tackle Vizing's conjecture.