Extra Connectivity of Strong Product of Graphs

Qinze Zhu; Yingzhi Tian

paper

Extra Connectivity of Strong Product of Graphs

arXiv:2306.15791

Abstract

The $g$ - $e x t r a$ $co nn ec t i v i t y$ $κ_{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 $s t r o n g$ $p r o d u c t$ $G_{1} ⊠ G_{2}$ of graphs $G_{1}$ and $G_{2}$ is the graph with vertex set $V (G_{1} ⊠ 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} ⊠ 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)$ - $e x t r a$ $co nn ec t i v i t y$ of $G_{1} ⊠ 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)$ - $e x t r a$ conditional fault-diagnosability of $G_{1} ⊠ G_{2}$ under $P M C$ model.