{
  "id": "2306.15791",
  "version": "v1",
  "published": "2023-06-27T20:40:38.000Z",
  "updated": "2023-06-27T20:40:38.000Z",
  "title": "Extra Connectivity of Strong Product of Graphs",
  "authors": [
    "Qinze Zhu",
    "Yingzhi Tian"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "The $g$-$extra$ $connectivity$ $\\kappa_{g}(G)$ of a connected graph $G$ is the minimum cardinality of a set of vertices, if it exists, whose deletion makes $G$ disconnected and leaves each remaining component with more than $g$ vertices, where $g$ is a non-negative integer. The $strong$ $product$ $G_1 \\boxtimes G_2$ of graphs $G_1$ and $G_2$ is the graph with vertex set $V(G_1 \\boxtimes G_2)=V(G_1)\\times V(G_2)$, where two distinct vertices $(x_{1}, y_{1}),(x_{2}, y_{2}) \\in V(G_1)\\times V(G_2)$ are adjacent in $G_1 \\boxtimes G_2$ if and only if $x_{1}=x_{2}$ and $y_{1} y_{2} \\in E(G_2)$ or $y_{1}=y_{2}$ and $x_{1} x_{2} \\in E(G_1)$ or $x_{1} x_{2} \\in E(G_1)$ and $y_{1} y_{2} \\in E(G_2)$. In this paper, we give the $g\\ (\\leq 3)$-$extra$ $connectivity$ of $G_1\\boxtimes G_2$, where $G_i$ is a maximally connected $k_i\\ (\\geq 2)$-regular graph for $i=1,2$. As a byproduct, we get $g\\ (\\leq 3)$-$extra$ conditional fault-diagnosability of $G_1\\boxtimes G_2$ under $PMC$ model.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-06-27T20:40:38.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "strong product",
      "extra connectivity",
      "minimum cardinality",
      "conditional fault-diagnosability",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}