{
  "id": "1512.07514",
  "version": "v1",
  "published": "2015-12-23T15:24:41.000Z",
  "updated": "2015-12-23T15:24:41.000Z",
  "title": "On the structure of dominating graphs",
  "authors": [
    "Saeid Alikhani",
    "Davood Fatehi",
    "Sandi Klavžar"
  ],
  "comment": "8 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "The $k$-dominating graph $D_k(G)$ of a graph $G$ is defined on the vertex set consisting of dominating sets of $G$ with cardinality at most $k$, two such sets being adjacent if they differ by either adding or deleting a single vertex. In this paper, after presenting several basic properties of $k$-dominating graphs, it is proved that if $G$ is a graph with no isolates, of order $n\\ge 2$, and with $G\\cong D_k(G)$, then $k=2$ and $G=K_{1,n-1}$ for some $n\\ge 4$. The problem of which graphs are dominating graphs is also considered. In particular it is shown that paths and cycles of order at least $5$ are not dominating graph. Some results on the order of dominating graphs are also obtained.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-23T15:24:41.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C62"
    ],
    "keywords": [
      "dominating graph",
      "single vertex",
      "basic properties",
      "vertex set consisting",
      "dominating sets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}