The 3-Good-Neighbor Connectivity of Modified Bubble-Sort Graphs

Let G=VG,EG be a connected graph. A subset F⊆VG is called a g-good-neighbor cut if G−F is disconnected and each vertex of G−F has at least g neighbors. The g-good-neighbor connectivity of G is the minimum cardinality of g-good-neighbor cuts. The n-dimensional modified bubble-sort graph MBn is a special Cayley graph. It has many good properties. In this paper, we prove that the 3-good-neighbor connectivity of MBn is 8n−24 for n≥6