{
  "id": "math/0602432",
  "version": "v1",
  "published": "2006-02-20T16:38:03.000Z",
  "updated": "2006-02-20T16:38:03.000Z",
  "title": "On the global offensive alliance number of a graph",
  "authors": [
    "J. M. Sigarreta",
    "J. A. Rodriguez"
  ],
  "journal": "Discrete Applied Mathematics 157 (2) (2009) 219-226",
  "categories": [
    "math.CO"
  ],
  "abstract": "An offensive alliance in a graph $\\Gamma=(V,E)$ is a set of vertices $S\\subset V$ where for every vertex $v$ in its boundary it holds that the majority of vertices in $v$'s closed neighborhood are in $S$. In the case of strong offensive alliance, strict majority is required. An alliance $S$ is called global if it affects every vertex in $V\\backslash S$, that is, $S$ is a dominating set of $\\Gamma$. The offensive alliance number $a_o(\\Gamma)$ (respectively, strong offensive alliance number $a_{\\hat{o}}(\\Gamma)$) is the minimum cardinality of an offensive (respectively, strong offensive) alliance in $\\Gamma$. The global offensive alliance number $\\gamma_o(\\Gamma)$ and the global strong offensive alliance number $\\gamma_{\\hat{o}}(\\Gamma)$ are defined similarly. Clearly, $a_o(\\Gamma)\\le \\gamma_o(\\Gamma)$ and $a_{\\hat{o}}(\\Gamma)\\le \\gamma_{\\hat{o}}(\\Gamma)$. It was shown in [Discuss. Math. Graph Theory, 24 (2004), no. 2, 263-275] that $ a_o(\\Gamma)\\le \\frac{2n}{3}$ and $ a_{\\hat{o}}(\\Gamma)\\le \\frac{5n}{6}$, where $n$ denotes the order of $\\Gamma$. In this paper we obtain several tight bounds on $\\gamma_o(\\Gamma)$ and $\\gamma_{\\hat{o}}(\\Gamma)$ in terms of several parameters of $\\Gamma$. For instance, we show that $\\frac{2m+n}{3\\Delta+1} \\le \\gamma_o(\\Gamma)\\le \\frac{2n}{3}$ and $\\frac{2(m+n)}{3\\Delta+2} \\le\\gamma_{\\hat{o}}(\\Gamma)\\le \\frac{5n}{6}$, where $m$ denotes the size of $\\Gamma$ and $\\Delta$ its maximum degree (the last upper bound holds true for all $\\Gamma$ with minimum degree greatest or equal to two).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-02-20T16:38:03.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "15C05"
    ],
    "keywords": [
      "global offensive alliance number",
      "global strong offensive alliance number",
      "upper bound holds true",
      "minimum degree greatest",
      "strict majority"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......2432S"
    }
  }
}