  Vizing's conjecture (open since 1968) relates the product of the domination
numbers of two graphs to the domination number of their Cartesian product
graph. In this paper, we formulate Vizing's conjecture as a Positivstellensatz
existence question. In particular, we select classes of graphs according to
their number of vertices and their domination number and encode the conjecture
as an ideal/polynomial pair such that the polynomial is non-negative on the
variety associated with the ideal if and only if the conjecture is true for
this graph class. Using semidefinite programming we obtain numeric
sum-of-squares certificates, which we then manage to transform into symbolic
certificates confirming non-negativity of our polynomials. Specifically, we
obtain exact low-degree sparse sum-of-squares certificates for particular
classes of graphs.
  The obtained certificates allow generalizations for larger graph classes.
Besides computational verification of these more general certificates, we also
present theoretical proofs as well as conjectures and questions for further
investigations.
