{
  "id": "1609.08885",
  "version": "v1",
  "published": "2016-09-28T12:33:18.000Z",
  "updated": "2016-09-28T12:33:18.000Z",
  "title": "On $g$-Extra Connectivity of Hypercube-like Networks",
  "authors": [
    "Jin-Xin Zhou"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a connected graph $G$ and a non-negative integer $g$, the {\\em $g$-extra connectivity} $\\k_g(G)$ of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose deletion disconnects $G$ and leaves each remaining component with more than $g$ vertices. This paper focuses on the $g$-extra connectivity of hypercube-like networks (HL-networks for short) which includes numerous well-known topologies, such as hypercubes, twisted cubes, crossed cubes and M\\\"obius cubes. All the known results suggest the equality $\\k_g(X_n)=f_n(g)$ holds, where $X_n$ is an $n$-dimensional HL-network, $f_n(g)=n(g+1)-\\frac{g(g+3)}{2}$, $n\\geq 5$ and $0\\leq g\\leq n-3$? Some authors also attempted to prove this equality in general. In this paper, we construct a subfamily of an $n$-dimensional HL-network with $g$-extra connectivity greater than $f_n(g)$ which implies that the above equality does not hold in general. We also prove that for $n\\geq 5$ and $0\\leq g\\leq n-3$, $\\k_g(X_n)\\geq f_n(g)$ always holds. This enables us to give a sufficient condition for the equality $\\k_g(X_n)=f_n(g)$, which is then used to determine the $g$-extra connectivity of HL-networks for some small $g$ or the $g$-extra connectivity of some particular subfamily of HL-networks. As a result, a short proof for the main results in [Journal of Computer and System Sciences 79 (2013) 669--688].",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-09-28T12:33:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hypercube-like networks",
      "dimensional hl-network",
      "extra connectivity greater",
      "deletion disconnects",
      "paper focuses"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}