Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gröbner Bases
Preprint
Abstract
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 $\mathcal{G}$ of all graphs with $n_\mathcal{G}$ vertices and domination number $k_\mathcal{G}$ and reformulated Vizing's conjecture as the problem that for all graph classes $\mathcal{G}$ and $\mathcal{H}$ 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 $k_\mathcal{G}$, $n_\mathcal{G}$, $k_\mathcal{H}$, and $n_\mathcal{H}$. In this paper, we consider their approach for $k_\mathcal{G} = k_\mathcal{H} = 1$. For this case we are able to derive the unique reduced Gr\"obner basis of the Vizing ideal. Based on this, we deduce the minimum degree $(n_\mathcal{G} + n_\mathcal{H} - 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 $\mathcal{G}$ and $\mathcal{H}$ with $n_\mathcal{G} + n_\mathcal{H} -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 $\mathcal{G}$ and $\mathcal{H}$ with $k_\mathcal{G}=k_\mathcal{H}=1$ and $n_\mathcal{G} + n_\mathcal{H} \leq 15$.
Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Towards a computational proof of Vizing's conjecture using semidefinite programming and sums-of-squaresJournal of Symbolic Computation, 2021
- Vizing's conjecture: a survey and recent resultsJournal of Graph Theory, 2011
- Expressing Combinatorial Problems by Systems of Polynomial Equations and Hilbert's NullstellensatzCombinatorics, Probability and Computing, 2009
- Algebraic characterization of uniquely vertex colorable graphsJournal of Combinatorial Theory, Series B, 2008
- Semidefinite representations for finite varietiesMathematical Programming, 2006
- Nowhere-zero flow polynomialsJournal of Combinatorial Theory, Series A, 2004
- On the Ideal Theory of GraphsJournal of Algebra, 1994
- Stable sets and polynomialsDiscrete Mathematics, 1994
- Symmetric polynomials and Hall's theoremDiscrete Mathematics, 1988
- Independence numbers of graphs and generators of idealsCombinatorica, 1981