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

Abstract EN

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.