{
  "id": "math/0602434",
  "version": "v1",
  "published": "2006-02-20T17:10:05.000Z",
  "updated": "2006-02-20T17:10:05.000Z",
  "title": "On defensive alliances and line graphs",
  "authors": [
    "J. M. Sigarreta",
    "J. A. Rodriguez"
  ],
  "journal": "Applied Mathematics Letters 19 (12) (2006) 1345-1350",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $\\Gamma$ be a simple graph of size $m$ and degree sequence $\\delta_1\\ge \\delta_2\\ge ... \\ge \\delta_n$. Let ${\\cal L}(\\Gamma)$ denotes the line graph of $\\Gamma$. The aim of this paper is to study mathematical properties of the alliance number, ${a}({\\cal L}(\\Gamma)$, and the global alliance number, $\\gamma_{a}({\\cal L}(\\Gamma))$, of the line graph of a simple graph. We show that $\\lceil\\frac{\\delta_{n}+\\delta_{n-1}-1}{2}\\rceil \\le {a}({\\cal L}(\\Gamma))\\le \\delta_1.$ In particular, if $\\Gamma$ is a $\\delta$-regular graph ($\\delta>0$), then $a({\\cal L}(\\Gamma))=\\delta$, and if $\\Gamma$ is a $(\\delta_1,\\delta_2)$-semiregular bipartite graph, then $a({\\cal L}(\\Gamma))=\\lceil \\frac{\\delta_1+\\delta_2-1}{2} \\rceil$. As a consequence of the study we compare $a({\\cal L}(\\Gamma))$ and ${a}(\\Gamma)$, and we characterize the graphs having $a({\\cal L}(\\Gamma))<4$. Moreover, we show that the global-connected alliance number of ${\\cal L}(\\Gamma)$ is bounded by $\\gamma_{ca}({\\cal L}(\\Gamma)) \\ge \\lceil\\sqrt{D(\\Gamma)+m-1}-1\\rceil,$ where $D(\\Gamma)$ denotes the diameter of $\\Gamma$, and we show that the global alliance number of ${\\cal L}(\\Gamma)$ is bounded by $\\gamma_{a}({\\cal L}(\\Gamma))\\geq \\lceil\\frac{2m}{\\delta_{1}+\\delta_{2}+1}\\rceil$. The case of strong alliances is studied by analogy.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-02-20T17:10:05.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "15C05"
    ],
    "keywords": [
      "line graph",
      "defensive alliances",
      "global alliance number",
      "simple graph",
      "semiregular bipartite graph"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006math......2434S"
    }
  }
}