{
  "id": "1402.1962",
  "version": "v2",
  "published": "2014-02-09T16:41:41.000Z",
  "updated": "2014-12-27T20:08:45.000Z",
  "title": "On Zero Forcing Number of Graphs and Their Complements",
  "authors": [
    "Linda Eroh",
    "Cong X. Kang",
    "Eunjeong Yi"
  ],
  "comment": "9 pages, 5 figures. arXiv admin note: text overlap with arXiv:1204.2238",
  "doi": "10.1142/S1793830915500020",
  "categories": [
    "math.CO"
  ],
  "abstract": "The \\emph{zero forcing number}, $Z(G)$, of a graph $G$ is the minimum cardinality of a set $S$ of black vertices (whereas vertices in $V(G) \\setminus S$ are colored white) such that $V(G)$ is turned black after finitely many applications of \"the color-change rule\": a white vertex is converted to a black vertex if it is the only white neighbor of a black vertex. Zero forcing number was introduced and used to bound the minimum rank of graphs by the \"AIM Minimum Rank -- Special Graphs Work Group\". It's known that $Z(G)\\geq \\delta(G)$, where $\\delta(G)$ is the minimum degree of $G$. We show that $Z(G)\\leq n-3$ if a connected graph $G$ of order $n$ has a connected complement graph $\\overline{G}$. Further, we characterize a tree or a unicyclic graph $G$ which satisfies either $Z(G)+Z(\\overline{G})=\\delta(G)+\\delta(\\overline{G})$ or $Z(G)+Z(\\overline{G})=2(n-3)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-02-09T16:41:41.000Z",
      "comment": "8 pages, 5 figures. arXiv admin note: text overlap with arXiv:1204.2238",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2014-12-27T20:08:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C50",
      "05C05",
      "05C38",
      "05D99"
    ],
    "keywords": [
      "zero forcing number",
      "complement",
      "black vertex",
      "special graphs work group",
      "aim minimum rank"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 9,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1402.1962E"
    }
  }
}