{
  "id": "2010.03219",
  "version": "v1",
  "published": "2020-10-07T06:56:56.000Z",
  "updated": "2020-10-07T06:56:56.000Z",
  "title": "Excellent graphs with respect to domination: subgraphs induced by minimum dominating sets",
  "authors": [
    "Vladimir Samodivkin"
  ],
  "comment": "13 pages, 2 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph $G=(V,E)$ is $\\gamma$-excellent if $V$ is a union of all $\\gamma$-sets of $G$, where $\\gamma$ stands for the domination number. Let $\\mathcal{I}$ be a set of all mutually nonisomorphic graphs and $\\emptyset \\not= \\mathcal{H} \\subsetneq \\mathcal{I}$. In this paper we initiate the study of the $\\mathcal{H}$-$\\gamma$-excellent graphs, which we define as follows. A graph $G$ is $\\mathcal{H}$-$\\gamma$-excellent if the following hold: (i) for every $H \\in \\mathcal{H}$ and for each $x \\in V(G)$ there exists an induced subgraph $H_x$ of $G$ such that $H$ and $H_x$ are isomorphic, $x \\in V(H_x)$ and $V(H_x)$ is a subset of some $\\gamma$-set of $G$, and (ii) the vertex set of every induced subgraph $H$ of $G$, which is isomorphic to some element of $\\mathcal{H}$, is a subset of some $\\gamma$-set of $G$. For each of some well known graphs, including cycles, trees and some cartesian products of two graphs, we describe its largest set $\\mathcal{H} \\subsetneq \\mathcal{I}$ for which the graph is $\\mathcal{H}$-$\\gamma$-excellent. Results on $\\gamma$-excellent regular graphs and a generalized lexicographic product of graphs are presented. Several open problems and questions are posed.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-10-07T06:56:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "minimum dominating sets",
      "excellent graphs",
      "induced subgraph",
      "excellent regular graphs",
      "open problems"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}