{
  "id": "1706.03682",
  "version": "v1",
  "published": "2017-06-12T15:21:30.000Z",
  "updated": "2017-06-12T15:21:30.000Z",
  "title": "Two inequalities related to Vizing's conjecture",
  "authors": [
    "Shira Zerbib"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A well-known conjecture of Vizing is that $\\gamma(G \\square H) \\ge \\gamma(G)\\gamma(H)$ for any pair of graphs $G, H$, where $\\gamma$ is the domination number and $G \\square H$ is the Cartesian product of $G$ and $H$. Suen and Tarr, improving a result of Clark and Suen, showed $\\gamma(G \\square H) \\ge \\frac{1}{2}\\gamma(G)\\gamma(H) + \\frac{1}{2}\\min(\\gamma(G),\\gamma(H))$. We further improve their result by showing $\\gamma(G \\square H) \\ge \\frac{1}{2}\\gamma(G)\\gamma(H) + \\frac{1}{2}\\max(\\gamma(G),\\gamma(H)).$ We also prove a fractional version of Vizing's conjecture: $\\gamma(G \\square H) \\ge \\gamma(G)\\gamma^*(H)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-06-12T15:21:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vizings conjecture",
      "inequalities",
      "well-known conjecture",
      "domination number",
      "cartesian product"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}