{
  "id": "math/0610023",
  "version": "v1",
  "published": "2006-09-30T15:23:39.000Z",
  "updated": "2006-09-30T15:23:39.000Z",
  "title": "Offensive alliances in cubic graphs",
  "authors": [
    "J. A. Rodriguez",
    "J. M. Sigarreta"
  ],
  "journal": "International Mathematical Forum 1 (36) (2006) 1773-1782",
  "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 global offensive alliance number $\\gamma_o(\\Gamma)$ (respectively, global strong offensive alliance number $\\gamma_{\\hat{o}}(\\Gamma)$) is the minimum cardinality of a global offensive (respectively, global strong offensive) alliance in $\\Gamma$. If $\\Gamma$ has global independent offensive alliances, then the \\emph{global independent offensive alliance number} $\\gamma_i(\\Gamma)$ is the minimum cardinality among all independent global offensive alliances of $\\Gamma$. In this paper we study mathematical properties of the global (strong) alliance number of cubic graphs. For instance, we show that for all connected cubic graph of order $n$, $$\\frac{2n}{5}\\le \\gamma_i(\\Gamma)\\le \\frac{n}{2}\\le \\gamma_{\\hat{o}}(\\Gamma)\\le \\frac{3n}{4} \\le \\gamma_{\\hat{o}}({\\cal L}(\\Gamma))=\\gamma_{o}({\\cal L}(\\Gamma))\\le n,$$ where ${\\cal L}(\\Gamma)$ denotes the line graph of $\\Gamma$. All the above bounds are tight.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-09-30T15:23:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "15C05"
    ],
    "keywords": [
      "cubic graph",
      "global strong offensive alliance number",
      "minimum cardinality",
      "independent global offensive alliances",
      "independent offensive alliance number"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math.....10023R"
    }
  }
}