{
  "id": "2208.08404",
  "version": "v1",
  "published": "2022-08-17T16:57:18.000Z",
  "updated": "2022-08-17T16:57:18.000Z",
  "title": "The $g$-extra connectivity of the strong product of paths and cycles",
  "authors": [
    "Qinze Zhu",
    "Yingzhi Tian"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $G$ be a connected graph and $g$ be a non-negative integer. The $g$-extra connectivity of $G$ is the minimum cardinality of a set of vertices in $G$, if it exists, whose removal disconnects $G$ and leaves every component with more than $g$ vertices. The strong product $G_1 \\boxtimes G_2$ of graphs $G_1=(V_{1}, E_{1})$ and $G_2=(V_{2}, E_{2})$ is the graph with vertex set $V(G_1 \\boxtimes G_2)=V_{1} \\times V_{2}$, where two distinct vertices $(x_{1}, x_{2}), (y_{1}, y_{2}) \\in V_{1} \\times V_{2}$ are adjacent in $G_1 \\boxtimes G_2$ if and only if $x_{i}=y_{i}$ or $x_{i} y_{i} \\in E_{i}$ for $i=1, 2$. In this paper, we obtain the $g$-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-08-17T16:57:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "strong product",
      "extra connectivity",
      "minimum cardinality",
      "removal disconnects",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}