{
  "id": "1805.08461",
  "version": "v1",
  "published": "2018-05-22T09:02:56.000Z",
  "updated": "2018-05-22T09:02:56.000Z",
  "title": "The restricted $h$-connectivity of balanced hypercubes",
  "authors": [
    "Huazhong Lü",
    "Tingzeng Wu"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The restricted $h$-connectivity of a graph $G$, denoted by $\\kappa^h(G)$, is defined as the minimum cardinality of a set of vertices $F$ in $G$, if exists, whose removal disconnects $G$ and the minimum degree of each component of $G-F$ is at least $h$. In this paper, we study the restricted $h$-connectivity of the balanced hypercube $BH_n$ and determine that $\\kappa^1(BH_n)=\\kappa^2(BH_n)=4n-4$ for $n\\geq2$. We also obtain a sharp upper bound of $\\kappa^3(BH_n)$ and $\\kappa^4(BH_n)$ of $n$-dimension balanced hypercube for $n\\geq3$ ($n\\neq4$). In particular, we show that $\\kappa^3(BH_3)=\\kappa^4(BH_3)=12$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-22T09:02:56.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R10",
      "05C40"
    ],
    "keywords": [
      "connectivity",
      "sharp upper bound",
      "dimension balanced hypercube",
      "removal disconnects",
      "minimum cardinality"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}