{
  "id": "1204.4018",
  "version": "v1",
  "published": "2012-04-18T08:58:17.000Z",
  "updated": "2012-04-18T08:58:17.000Z",
  "title": "Fault Diagnosability of Arrangement Graphs",
  "authors": [
    "Shuming Zhou",
    "Jun-Ming Xu"
  ],
  "comment": "21 pages, 2 figures, 37 refrences",
  "categories": [
    "math.CO"
  ],
  "abstract": "The growing size of the multiprocessor system increases its vulnerability to component failures. It is crucial to locate and to replace the faulty processors to maintain a system's high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all remaining vertices in the $(n,k)$-arrangement graph $A_{n,k}$ when the number of moved faulty vertices is up to twice or three times the traditional connectivity. Based on this fault resiliency, we establishes that the conditional diagnosability of $A_{n,k}$ under the comparison model. We prove that for $k\\geq 4$, $n\\geq k+2$, the conditional diagnosability of $A_{n,k}$ is $(3k-2)(n-k)-3$; the conditional diagnosability of $A_{n,n-1}$ is $3n-7$ for $n\\geq 5$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-04-18T08:58:17.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "arrangement graph",
      "fault diagnosability",
      "conditional diagnosability",
      "multiprocessor system increases",
      "systems high reliability"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1204.4018Z"
    }
  }
}