{
  "id": "1308.3210",
  "version": "v1",
  "published": "2013-08-14T19:00:25.000Z",
  "updated": "2013-08-14T19:00:25.000Z",
  "title": "Bounds on the Maximum Number of Minimum Dominating Sets",
  "authors": [
    "Samuel Connolly",
    "Zachary Gabor",
    "Anant Godbole",
    "Bill Kay"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "We use probabilistic methods to find lower bounds on the maximum number, in a graph with domination number \\gamma, of dominating sets of size \\gamma. We find that we can randomly generate a graph that, w.h.p., is dominated by almost all sets of size \\gamma. At the same time, we use a modified adjacency matrix to obtain lower bounds on the number of sets of a given size that do not dominate a graph on n vertices",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-08-14T19:00:25.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "minimum dominating sets",
      "maximum number",
      "lower bounds",
      "probabilistic methods",
      "domination number"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1308.3210C"
    }
  }
}