The g-extra connectivity of graph products
Zhao Wang, Yaping Mao, Sun‐Yuan Hsieh, Ralf Klasing, Yuzhi Xiao
Abstract
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.