{
  "id": "2112.04007",
  "version": "v3",
  "published": "2021-12-07T21:38:31.000Z",
  "updated": "2023-06-21T11:31:54.000Z",
  "title": "Sum-of-Squares Certificates for Vizing's Conjecture via Determining Gröbner Bases",
  "authors": [
    "Elisabeth Gaar",
    "Melanie Siebenhofer"
  ],
  "comment": "36 pages, 2 figures",
  "categories": [
    "math.CO",
    "math.OC"
  ],
  "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$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2023-06-21T11:31:54.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "90C27",
      "05C99",
      "13P10",
      "68W30",
      "90C22"
    ],
    "keywords": [
      "vizings conjecture",
      "determining gröbner bases",
      "graph class",
      "sum-of-squares certificates",
      "domination number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 36,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}