{
  "id": "1209.5138",
  "version": "v2",
  "published": "2012-09-24T02:19:22.000Z",
  "updated": "2013-03-01T20:26:59.000Z",
  "title": "The $k$-Dominating Graph",
  "authors": [
    "Ruth Haas",
    "Karen Seyffarth"
  ],
  "comment": "2 figure, The final publication is available at http://link.springer.com",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a graph $G$, the $k$-dominating graph of $G$, $D_k(G)$, is defined to be the graph whose vertices correspond to the dominating sets of $G$ that have cardinality at most $k$. Two vertices in $D_k(G)$ are adjacent if and only if the corresponding dominating sets of $G$ differ by either adding or deleting a single vertex. The graph $D_k(G)$ aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of $D_k(G)$. In this paper we give conditions that ensure $D_k(G)$ is connected.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-03-01T20:26:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dominating graph",
      "single vertex additions",
      "reconfiguration problem",
      "intermediate set",
      "vertices correspond"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1209.5138H"
    }
  }
}