The g-extra connectivity of graph products
Zhao Wang, Yaping Mao, Sun‐Yuan Hsieh, Ralf Klasing, Yuzhi Xiao · Journal of Computer and System Sciences · 2024
Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is said to be a cutset if G−S is not connected. A cutset S is called an Rg-cutset, where g is a non-negative integer, if every component of G−S has at least g+1 vertices. If G has at least one Rg-cutset, the g-extra connectivity of G, denoted by κg(G), is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two general graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.