{
  "id": "1608.02107",
  "version": "v1",
  "published": "2016-08-06T13:21:54.000Z",
  "updated": "2016-08-06T13:21:54.000Z",
  "title": "A new bound for Vizing's conjecture",
  "authors": [
    "Elliot Krop"
  ],
  "comment": "7 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "For any graph $G$, we define the power $\\pi(G)$ as the minimum of the largest number of neighbors in a $\\gamma$-set of $G$, of any vertex, taken over all $\\gamma$-sets of $G$. We show that $\\gamma(G\\square H)\\geq \\frac{\\pi(G)}{2\\pi(G) -1}\\gamma(G)\\gamma(H)$. This implies that for any graphs $G$ and $H$, $\\gamma(G\\square H)\\geq \\frac{\\gamma(G)}{2\\gamma(G)-1}\\gamma(G)\\gamma(H)$, and if $G$ is claw-free or $P_4$-free, $\\gamma(G\\square H)\\geq \\frac{2}{3}\\gamma(G)\\gamma(H)$, where $\\gamma(G)$ is the domination number of $G$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-08-06T13:21:54.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vizings conjecture",
      "domination number",
      "largest number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 7,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}