Sum-of-squares certificates for Vizing's conjecture via determining Grobner bases

The famous open Vizing conjecture claims that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recently Gaar, Krenn, Margulies and Wiegele used the graph class g of all graphs with ng vertices and domination number kg and reformulated Vizing's conjecture as the problem that for all graph classes g and 7-t the Vizing polynomial is sum-of-squares (SOS) modulo the Vizing ideal. By solving semidefinite programs (SDPs) and clever guessing they derived SOS-certificates for some values of kg, ng, kn, and nn. In this paper, we consider their approach for kg = kn= 1. For this case we are able to derive the unique reduced Grobner basis of the Vizing ideal. Based on this, we deduce the minimum degree (ng +nn -1)/2 of an SOS-certificate for Vizing's conjecture, which is the first result of this kind. Furthermore, we present a method to find certificates for graph classes g and 7-t with ng +nn -1 = d for general d, which is again based on solving SDPs, but does not depend on guessing and depends on much smaller SDPs. We implement our new method in SageMath and give new SOS certificates for all graph classes g and 7-t with kg = kn= 1 and ng +nn & LE; 15.& COPY; 2023 The Author(s). Published by Elsevier Ltd. This is an open access article under the CC BY license (http:// creativecommons .org /licenses /by /4 .0/).

Automated summary

The open Vizing conjecture states that the domination number of the Cartesian product graph of two graphs G and H is at least the product of the domination numbers of G and H. Recent research reformulated this conjecture using the graph class g and introduced the concept of SOS-certificates. By solving semidefinite programs (SDPs) and applying clever guessing, they obtained SOS-certificates for specific cases. In this paper, we consider their approach for a specific case and derive the unique reduced Grobner basis of the Vizing ideal, which leads to the minimum degree of an SOS-certificate. We also propose a method to find certificates for general cases, which relies on solving smaller SDPs and does not require guessing. We provide new SOS-certificates for various graph classes using our implemented method in SageMath.