New Sum-Of-Squares Certificates for Vizing’s Conjecture

Vizing’s conjecture is an open famous graph-theoretical problem stated in 1968 by the mathematician Vadim Vizing. It claims that the domination number of the cartesian product graph of two graphs G and H is at least as large as the product of the domination numbers of G and H. In 2019 Gaar, Krenn, Margulies, and Wiegele presented a new method to potentially prove the conjecture. Their approach is based on ideal theory and semidefinite programming. More precisely, they reformulated Vizing’s conjecture as a sum-of-squares problem for graph classes with fixed number of vertices and minimum dominating sets. They successfully derived sum-of-squares certificates for some graph
 classes with high domination numbers.
 In this talk, we consider their approach for graph classes with domination number 1. We can derive the reduced Gröbner basis for this particular case, which allows us to state the minimum degree of a
 sum-of-squares certificate for Vizing’s conjecture. We further present a method to find certificates for these graph classes, which is again based on solving semidefinite programs.