DIKUL - logo
E-viri
Celotno besedilo
Recenzirano
  • The g-extra connectivity of...
    Wang, Zhao; Mao, Yaping; Hsieh, Sun-Yuan; Klasing, Ralf; Xiao, Yuzhi

    Journal of computer and system sciences, November 2024, 2024-11-00, Letnik: 145
    Journal Article

    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.