{
  "id": "1701.08355",
  "version": "v1",
  "published": "2017-01-29T08:35:52.000Z",
  "updated": "2017-01-29T08:35:52.000Z",
  "title": "Equal relation between the extra connectivity and pessimistic diagnosability for some regular graphs",
  "authors": [
    "Mei-Mei Gu",
    "Rong-Xia Hao",
    "Jun-Ming Xu",
    "Yan-Quan Feng"
  ],
  "comment": "23 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Extra connectivity and the pessimistic diagnosis are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processor. The pessimistic diagnosis strategy is a classic strategy based on the PMC model in which isolates all faulty vertices within a set containing at most one fault-free vertex. In this paper, the result that the pessimistic diagnosability $t_p(G)$ equals the extra connectivity $\\kappa_{1}(G)$ of a regular graph $G$ under some conditions are shown. Furthermore, the following new results are gotten: the pessimistic diagnosability $t_p(S_n^2)=4n-9$ for split-star networks $S_n^2$, $t_p(\\Gamma_n)=2n-4$ for Cayley graphs generated by transposition trees $\\Gamma_n$, $t_p(\\Gamma_{n}(\\Delta))=4n-11$ for Cayley graph generated by the $2$-tree $\\Gamma_{n}(\\Delta)$, $t_{p}(BP_n)=2n-2$ for the burnt pancake networks $BP_n$. As corollaries, the known results about the extra connectivity and the pessimistic diagnosability of many famous networks including the alternating group graphs, the alternating group networks, BC networks, the $k$-ary $n$-cube networks etc. are obtained directly.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-01-29T08:35:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R10",
      "G.2.2"
    ],
    "keywords": [
      "extra connectivity",
      "pessimistic diagnosability",
      "regular graph",
      "equal relation",
      "cayley graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 23,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}