{
  "id": "1601.02099",
  "version": "v1",
  "published": "2016-01-09T12:06:15.000Z",
  "updated": "2016-01-09T12:06:15.000Z",
  "title": "Dynamic Monopolies for Degree Proportional Thresholds in Connected Graphs of Girth at least Five and Trees",
  "authors": [
    "Dieter Rautenbach"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a graph, and let $\\rho\\in (0,1)$. For a set $D$ of vertices of $G$, let the set $H_{\\rho}(D)$ arise by starting with the set $D$, and iteratively adding further vertices $u$ to the current set if they have at least $\\lceil \\rho d_G(u)\\rceil$ neighbors in it. If $H_{\\rho}(D)$ contains all vertices of $G$, then $D$ is known as an irreversible dynamic monopoly or a perfect target set associated with the threshold function $u\\mapsto \\lceil \\rho d_G(u)\\rceil$. Let $h_{\\rho}(G)$ be the minimum cardinality of such an irreversible dynamic monopoly. For a connected graph $G$ of maximum degree at least $\\frac{1}{\\rho}$, Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed $h_{\\rho}(G)\\leq 5.83\\rho n(G)$, which was improved by Chang and Lyuu (Triggering cascades on strongly connected directed graphs, Theoretical Computer Science 593 (2015) 62-69) to $h_{\\rho}(G)\\leq 4.92\\rho n(G)$. We show that for every $\\epsilon>0$, there is some $\\rho(\\epsilon)>0$ such that $h_{\\rho}(G) \\leq(2+\\epsilon)\\rho n(G)$ for every $\\rho$ in $(0,\\rho(\\epsilon))$, and every connected graph $G$ that has maximum degree at least $\\frac{1}{\\rho}$ and girth at least $5$. Furthermore, we show that $h_{\\rho}(T) \\leq \\frac{2\\rho}{1+\\rho}n(T)$ for every $\\rho$ in $(0,1]$, and every tree $T$ that has maximum degree at least $\\frac{1}{\\rho}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-01-09T12:06:15.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "connected graph",
      "degree proportional thresholds",
      "dynamic monopolies",
      "maximum degree",
      "irreversible dynamic"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160102099G"
    }
  }
}