{
  "id": "1709.05052",
  "version": "v1",
  "published": "2017-09-15T04:11:08.000Z",
  "updated": "2017-09-15T04:11:08.000Z",
  "title": "Roman domination: changing, unchanging, $γ_R$-graphs",
  "authors": [
    "Vladimir Samodivkin"
  ],
  "comment": "19 pages, 3 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "A Roman dominating function (RD-function) on a graph $G = (V(G), E(G))$ is a labeling $f : V(G) \\rightarrow \\{0, 1, 2\\}$ such that every vertex with label $0$ has a neighbor with label $2$. The weight $f(V(G))$ of a RD-function $f$ on $G$ is the value $\\Sigma_{v\\in V(G)} f (v)$. The {\\em Roman domination number} $\\gamma_{R}(G)$ of $G$ is the minimum weight of a RD-function on $G$. The six classes of graphs resulting from the changing or unchanging of the Roman domination number of a graph when a vertex is deleted, or an edge is deleted or added are considered. We consider relationships among the classes, which are illustrated in a Venn diagram. A graph $G$ is Roman domination $k$-critical if the removal of any set of $k$ vertices decreases the Roman domination number. Some initial properties of these graphs are studied. The $\\gamma_R$-graph of a graph $G$ is any graph which vertex set is the collection $\\mathscr{D}_R(G)$ of all minimum weight RD-functions on $G$. We define adjacency between any two elements of $\\mathscr{D}_R(G)$ in several ways, and initiate the study of the obtained $\\gamma_R$-graphs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-15T04:11:08.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69"
    ],
    "keywords": [
      "roman domination number",
      "minimum weight rd-functions",
      "unchanging",
      "venn diagram",
      "vertices decreases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}