{
  "id": "0909.3695",
  "version": "v1",
  "published": "2009-09-21T06:53:32.000Z",
  "updated": "2009-09-21T06:53:32.000Z",
  "title": "An Improvement on Vizing's Conjecture",
  "authors": [
    "Yunjian Wu"
  ],
  "comment": "4 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\gamma(G)$ denote the domination number of a graph $G$. A {\\it Roman domination function} of a graph $G$ is a function $f: V\\to\\{0,1,2\\}$ such that every vertex with 0 has a neighbor with 2. The {\\it Roman domination number} $\\gamma_R(G)$ is the minimum of $f(V(G))=\\Sigma_{v\\in V}f(v)$ over all such functions. Let $G\\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\\gamma(G)\\gamma(H) \\leq \\gamma_R(G\\square H)$ for all simple graphs $G$ and $H$, which is an improvement of $\\gamma(G)\\gamma(H) \\leq 2\\gamma(G\\square H)$ given by Clark and Suen \\cite{CS}, since $\\gamma(G\\square H)\\leq \\gamma_R(G\\square H)\\leq 2\\gamma(G\\square H)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-09-21T06:53:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "vizings conjecture",
      "improvement",
      "roman domination function",
      "roman domination number",
      "simple graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 4,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0909.3695W"
    }
  }
}