  Vizing's conjecture (open since 1968) relates the sizes of dominating sets in
two graphs to the size of a dominating set in their Cartesian product graph. In
this paper, we formulate Vizing's conjecture itself as a Positivstellensatz
existence question. In particular, we encode the conjecture as an
ideal/polynomial pair such that the polynomial is nonnegative if and only if
the conjecture is true. We demonstrate how to use semidefinite optimization
techniques to computationally obtain numeric sum-of-squares certificates, and
then show how to transform these numeric certificates into symbolic
certificates approving nonnegativity of our polynomial.
  After outlining the theoretical structure of this computer-based proof of
Vizing's conjecture, we present computational and theoretical results. In
particular, we present exact low-degree sparse sum-of-squares certificates for
particular families of graphs.
