{
  "id": "1508.02173",
  "version": "v1",
  "published": "2015-08-10T09:05:12.000Z",
  "updated": "2015-08-10T09:05:12.000Z",
  "title": "Relationship between Conditional Diagnosability and 2-extra Connectivity of Symmetric Graphs",
  "authors": [
    "Rong-Xia Hao",
    "Zeng-Xian Tian",
    "Jun-Ming Xu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The conditional diagnosability and the 2-extra connectivity are two important parameters to measure ability of diagnosing faulty processors and fault-tolerance in a multiprocessor system. The conditional diagnosability $t_c(G)$ of $G$ is the maximum number $t$ for which $G$ is conditionally $t$-diagnosable under the comparison model, while the 2-extra connectivity $\\kappa_2(G)$ of a graph $G$ is the minimum number $k$ for which there is a vertex-cut $F$ with $|F|=k$ such that every component of $G-F$ has at least $3$ vertices. A quite natural problem is what is the relationship between the maximum and the minimum problem? This paper partially answer this problem by proving $t_c(G)=\\kappa_2(G)$ for a regular graph $G$ with some acceptable conditions. As applications, the conditional diagnosability and the 2-extra connectivity are determined for some well-known classes of vertex-transitive graphs, including, star graphs, $(n,k)$-star graphs, alternating group networks, $(n,k)$-arrangement graphs, alternating group graphs, Cayley graphs obtained from transposition generating trees, bubble-sort graphs, $k$-ary $n$-cube networks and dual-cubes. Furthermore, many known results about these networks are obtained directly.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-10T09:05:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "conditional diagnosability",
      "symmetric graphs",
      "connectivity",
      "relationship",
      "star graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150802173H"
    }
  }
}