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

Authors: Yanling Wang; Shiying Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

LetG=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.


---

## Body

## 1. Introduction

A multiprocessor system is modeled as an undirected graphG=V,E, whose vertices represent processors and edges represent communication links. Because of a significant increase in the number of processors, the processor failure is inevitable. Hence, fault diagnosis and fault tolerance of interconnection networks have become increasingly important [1, 2]. The modified bubble-sort graph has been studied by many researchers [3–5]. The features of the modified bubble-sort graph include low degree of vertices, symmetry, and high degree of fault tolerance. For details, see [3]. Recently, Wang et al. [6] studied the 2-good-neighbor connectivity and 2-good-neighbor diagnosability of bubble-sort star graph networks. Yu and Huang [4] proved that the 2-extra vertex connectivity of the modified bubble-sort graph was 3n−5. And they also got the 2-good-neighbor connectivity of the modified bubble-sort graph was 4n−8 when n≥4 [5]. In this paper, we study the 3-good-neighbor connectivity of the modified bubble-sort graph MBn for n≥6.


## 2. Preliminaries

In this section, some definitions and notations needed for our discussion are introduced.


### 2.1. Definitions and Notations

LetG=V,E be a graph and S⊆VG be a nonempty subset. The induced subgraph GS is the graph whose vertex set is S and the edge set is the set of all the edges of G with both endpoints in S. The degree dGv of a vertex v is the number of edges incident with v, with loops counted twice. The minimum degree of vertices in G is denoted by δG. For any vertex v, NGv is the neighborhood of v in G which is the set of vertices adjacent to v. u is called a neighbor vertex of v when u∈NGv. Let S⊆V, and we use NGS to denote the set ∪v∈SNGv\S. The girth of G is the length of the shortest cycle in G. A k-regular graph is a graph with each vertex having the same degree of k. A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and one end in Y; such a partition X,Y is called a bipartition of the graph, where X and Y are its parts. Let G=X,Y;E be a bipartite graph G with partition X,Y. If G=X,Y;E is simple and every vertex in X is joined to every vertex in Y, then G=X,Y;E is called a complete bipartite graph, denoted by Kn,m, where X=n and Y=m. A vertex cut of a connected graph G is a set of vertices whose removal renders G disconnected or only one vertex left. The vertex connectivity κG is the size of a minimal vertex cut. A graph is called κ-connected if its vertex connectivity is κ or greater. A faulty set F⊆VG is called a g-good-neighbor faulty set of G if each vertex u∈VG\F has at least g good neighbors in G−F; in other words, the minimum degree δ of G−F satisfies δG−F≥g. A g-good-neighbor cut of a graph G is a g-good-neighbor faulty set F such that G−F is disconnected. The g-good-neighbor connectivity of G is denoted by κgG, and it is the minimum cardinality of g-good-neighbor cuts. For graph-theoretical terminology and notations which do not be defined here, we follow [7].


### 2.2. The Modified Bubble-Sort Graph

The modified bubble-sort graph has been known as a famous topology structure of interconnection networks. In this section, its definition and some useful properties are introduced.LetΓ be a finite group and S be a spanning set of Γ which does not have identity element. The directed Cayley graph CayΓ,S is defined as follows: its vertex set is Γ, and its arc set is g,gs:g∈Γ,s∈S. If for each s∈S we also have s−1∈S, then we say that this Cayley graph is an undirected Cayley graph. Every Cayley graph in this paper is an undirected Cayley graph. The product στ of two permutations is the composition function τ followed by σ, that is, 1213=132.Let1,n=1,2,…,n. In this paper, we consider the Cayley graph CaySn,T, where Sn is the symmetric group on 1,n and T is a set of transpositions of Sn. Let GT be the graph on n vertices such that there is an edge ij in GT if and only if the transposition ij∈T. The graph GT is called the transposition generating graph of CaySn,T. When GT is a tree, it is denoted by Γn. In particular, when GT is a path, CaySn,T is the n-dimensional bubble-sort graph Bn [8]. When GT is a cycle, CaySn,T is the n-dimensional modified bubble-sort graph MBn [3]. Both MBn and Bn have the vertex set consisting of all n! permutations of 1,n. Two vertices u1 and v1 are adjacent in MBn if and only if v1=u1i,i+1 or v1=u11n for all 1≤i≤n−1. Two vertices u2 and v2 are adjacent in Bn if and only if v2=u2i,i+1 for all 1≤i≤n−1. Let GT be cycle of (123…n1). If we delete vertex n from the cycle GT, then it results in a path on n−1 vertices, and all edges of GT−n are the generating set of Sn−1. We can partition MBn into n subgraphs MBn1,MBn2,…,MBnn, where each vertex u=x1,x2,…,xn∈VMBn has a fixed integer i in the last position xn for i∈1,n. It is easy to verify MBni≅Bn−1. Bn is well studied by other researchers [9–13]. Bn has some small hypercubes Qk as subgraphs [14]. The hypercube Qn of dimension n is the graph whose vertex set is 0,1n (an n-bit character consisting of 0, 1) and where two vertices are adjacent if they differ in exactly one coordinate [15]. Qn has 2n vertices and 2n−1n edges. It is n-regular. Any vertex u∈VMBnr has two neighbors in MBni and MBnj which are called the outside neighbors of u where i,j,r∈1,n and i,j,r differ from each other. Let N′u=u+,u− be the two outside neighbors of u, in which u+ and u− are the labels of u1n and un−1,n, respectively. Let F⊆VMBn be a faulty set and let Fi=F∩VMBni. Let Ft,s=Ft+Ft+1+⋯+Fs, MBnt,s=MBnVMBnt∪VMBnt+1∪⋯∪VMBns, and MBnt,s−Ft,s=MBnVMBnt−Ft∪VMBnt+1−Ft+1∪⋯∪VMBns−Fs for t,s∈1,n and t<s. When we decompose Bn into n subgraphs Bn1,Bn2,…,Bnn along the last position, where each vertex u∈VBni has a fixed integer i in the last position for i∈1,n, then Bni≅Bn−1. Similar to the above, let Bnt,s=BnVBnt∪VBnt+1∪⋯∪VBns, Bnt,s−Ft,s=BnVBnt−Ft∪VBnt+1−Ft+1∪⋯∪VBns−Fs for t,s∈1,n and t<s.The graphs ofMB3, MB4, B3, B4, and Q3 are given in Figures 1–3.Figure 1
The modified bubble-sort graphs of MB3 and MB4.Figure 2
The bubble-sort graphs ofB3 and B4.Figure 3
The hypercubeQn of n=3.Remark 1.
Figure1 is general; it can be used in a different way, e.g., article “The 2-good-neighbor diagnosability of modified bubble-sort graphs under the PMC and MM∗ model” where we studied the 2-good-neighbor diagnosability which is the maximum number of faulty vertices that the system can ensure to identify under the condition that every fault-free vertex has at least 2 fault-free neighbors.


### 2.3. The Propositions ofMBn and Bn

The automorphism group of a graphG is transitive if there exists an automorphism φ to any pair u, v of vertices in G such that φu=v. In this case, G is called vertex transitive. Note that MBn is a special Cayley graph.Proposition 1 (see [3]).
For any integern≥3, MBn is vertex transitive and bipartite.Proposition 2 (see [10]).
For any integern≥2, Bn is vertex transitive and bipartite.Proposition 3 (see [4]).
For any integern≥3, the girth of MBn is 4.Proposition 4 (see [5]).
For any two distinct verticesu and v in MBn, Nu∩Nv≤2, when uv∉EMBn; Nu∩Nv=0, when uv∈EMBn for n≥4.
The edges whose end vertices in differentMBni’s are called cross-edges. Two edges are said to be independent if they are not adjacent.Proposition 5 (see [5]).
LetMBni and MBnj be defined as above. There are exactly 2n−2! independent cross-edges between MBni and MBnj for i,j∈1,n and i≠j.Proposition 6 (see [5]).
For anyu,v∈VMBni, each of u and v has two distinct outside neighbors, u+,u−∩v+,v−=∅ for i∈1,n.Proposition 7.
For any vertexu∈VMBn1,2, u+∈VMBn3,n or u−∈VMBn3,n.Proof.
Letu∈VMBn1,2, without loss of generality, let u=u1u2…un−11∈VMBn1. By the definition of MBn, u+=1u2…un−1u1 and u−=u1u2…1un−1. Note that u1≠1, un−1≠1 and u1≠un−1. Therefore, u+ or u−∈VMBn3,n.Proposition 8 (see [5]).
For any vertexu∈VMBnr, u+∈VMBni and u−∈VMBnj, where r,i,j∈1,n and r,i,j differ from each other.Proposition 9 (see [16]).
Each vertexu∈VBni has a unique outside neighbor for i∈1,n.Proposition 10 (see [16]).
LetBni and Bnj be defined as above. There are exactly n−2! independent cross-edges between Bni and Bnj for i,j∈1,n and i≠j.Proposition 11 (see [16]).
For any two distinct verticesu and v in Bni, they have different outside neighbors for i∈1,n.Proposition 12 (see [17]).
For any two distinct verticesu and v in Bn, Nu∩Nv≤2, when uv∉EBn; Nu∩Nv=0, when uv∈EBn.Proposition 13 (see [14]).
Letv1v2v3v4v1 be a 4-cycle in Bn. Then v2=v1i,i+1, v3=v2j,j+1, v4=v3i,i+1, and v1=v4j,j+1 for i,j∈1,n and i−j>1.Proposition 14 (see [14]).
Every 6-cycle inBn is in one of the following three types:(1)
i,i+1j,j+1i,i+1j,j+1i,i+1j,j+1 for i−j=1.(2)
i,i+1k,k+1i,i+1j,j+1k,k+1j,j+1 for i and j are related, and they are both unrelated with k.(3)
i,i+1j,j+1k,k+1i,i+1j,j+1k,k+1 or i,i+1j,j+1k,k+1i,i+1k,k+1j,j+1 or i,i+1j,j+1k,k+1j,j+1i,i+1k,k+1 for i,j,andk are all mutually unrelated.Proposition 15 (see [5]).
κ2MBn=4n−8 for n≥3.Proposition 16 (see [13]).
κ1Bn=2n−4 for n≥3.Proposition 17 (see [17]).
κ2Bn=4n−3 for n≥3.Proposition 18 (see [14]).
κ3B5=12; κ3Bn=8n−32 for n≥6.Proposition 19 (see [12]).
κBn=n−1.Proposition 20 (see [7]).
For a graphG=V,E, κG≤δG.Proposition 21.
κMBn=n.Proof.
SinceMB3≅K3,3 by Figure 1, we have κMB3=3. We will prove κMBn=n when n≥4. Note that MBn is n-regular. So, δMBn=n. Combining this with Proposition 20, we have that κMBn≤δMBn=n. Let F⊆VMBn and F≤n−1. For the purpose of proving κMBn≥n, it is sufficient to prove that MBn−F is connected when F≤n−1. We decompose MBn along the last position, denoted by MBni for i∈1,n. Note that MBni≅Bn−1 for i∈1,n. Let Fi=F∩VMBni and F1=maxFi:1≤i≤n for i∈1,n.Case 1.F1<n−2.Note thatMBni≅Bn−1. We have κMBni=n−2 by Proposition 19. Combining this with F1=maxFi:1≤i≤n, we have that MBni−Fi is connected for i∈1,n. By Proposition 5, there are 2n−2! independent cross-edges between two different MBni’s and 2n−2!>n−1 for n≥4, and we have that MBnVMBni−Fi∪VMBnj−Fj is connected for i,j∈1,n and i≠j. Thus, MBn−F is connected.Case 2.n−2≤F1≤n−1.In this case,F2,n≤1. By Proposition 19, MBnj−Fj is connected for j∈2,n. Since 2n−2!>1≥Fr+Fs for r,s∈2,n and r≠s, we have that MBnVMBnr−Fr∪VMBns−Fs is connected by Proposition 5. Thus, MBn2,n−F2,n is connected. By Proposition 8, each vertex u∈VMBn1−F1 has at least one outside neighbor in MBn2,n−F2,n. Thus, MBn−F is connected.
By Cases 1 and 2,F is not a cut of MBn for F≤n−1. So, κMBn≥n. Combining this with κMBn≤n, we have κMBn=n.


## 2.1. Definitions and Notations

LetG=V,E be a graph and S⊆VG be a nonempty subset. The induced subgraph GS is the graph whose vertex set is S and the edge set is the set of all the edges of G with both endpoints in S. The degree dGv of a vertex v is the number of edges incident with v, with loops counted twice. The minimum degree of vertices in G is denoted by δG. For any vertex v, NGv is the neighborhood of v in G which is the set of vertices adjacent to v. u is called a neighbor vertex of v when u∈NGv. Let S⊆V, and we use NGS to denote the set ∪v∈SNGv\S. The girth of G is the length of the shortest cycle in G. A k-regular graph is a graph with each vertex having the same degree of k. A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and one end in Y; such a partition X,Y is called a bipartition of the graph, where X and Y are its parts. Let G=X,Y;E be a bipartite graph G with partition X,Y. If G=X,Y;E is simple and every vertex in X is joined to every vertex in Y, then G=X,Y;E is called a complete bipartite graph, denoted by Kn,m, where X=n and Y=m. A vertex cut of a connected graph G is a set of vertices whose removal renders G disconnected or only one vertex left. The vertex connectivity κG is the size of a minimal vertex cut. A graph is called κ-connected if its vertex connectivity is κ or greater. A faulty set F⊆VG is called a g-good-neighbor faulty set of G if each vertex u∈VG\F has at least g good neighbors in G−F; in other words, the minimum degree δ of G−F satisfies δG−F≥g. A g-good-neighbor cut of a graph G is a g-good-neighbor faulty set F such that G−F is disconnected. The g-good-neighbor connectivity of G is denoted by κgG, and it is the minimum cardinality of g-good-neighbor cuts. For graph-theoretical terminology and notations which do not be defined here, we follow [7].


## 2.2. The Modified Bubble-Sort Graph

The modified bubble-sort graph has been known as a famous topology structure of interconnection networks. In this section, its definition and some useful properties are introduced.LetΓ be a finite group and S be a spanning set of Γ which does not have identity element. The directed Cayley graph CayΓ,S is defined as follows: its vertex set is Γ, and its arc set is g,gs:g∈Γ,s∈S. If for each s∈S we also have s−1∈S, then we say that this Cayley graph is an undirected Cayley graph. Every Cayley graph in this paper is an undirected Cayley graph. The product στ of two permutations is the composition function τ followed by σ, that is, 1213=132.Let1,n=1,2,…,n. In this paper, we consider the Cayley graph CaySn,T, where Sn is the symmetric group on 1,n and T is a set of transpositions of Sn. Let GT be the graph on n vertices such that there is an edge ij in GT if and only if the transposition ij∈T. The graph GT is called the transposition generating graph of CaySn,T. When GT is a tree, it is denoted by Γn. In particular, when GT is a path, CaySn,T is the n-dimensional bubble-sort graph Bn [8]. When GT is a cycle, CaySn,T is the n-dimensional modified bubble-sort graph MBn [3]. Both MBn and Bn have the vertex set consisting of all n! permutations of 1,n. Two vertices u1 and v1 are adjacent in MBn if and only if v1=u1i,i+1 or v1=u11n for all 1≤i≤n−1. Two vertices u2 and v2 are adjacent in Bn if and only if v2=u2i,i+1 for all 1≤i≤n−1. Let GT be cycle of (123…n1). If we delete vertex n from the cycle GT, then it results in a path on n−1 vertices, and all edges of GT−n are the generating set of Sn−1. We can partition MBn into n subgraphs MBn1,MBn2,…,MBnn, where each vertex u=x1,x2,…,xn∈VMBn has a fixed integer i in the last position xn for i∈1,n. It is easy to verify MBni≅Bn−1. Bn is well studied by other researchers [9–13]. Bn has some small hypercubes Qk as subgraphs [14]. The hypercube Qn of dimension n is the graph whose vertex set is 0,1n (an n-bit character consisting of 0, 1) and where two vertices are adjacent if they differ in exactly one coordinate [15]. Qn has 2n vertices and 2n−1n edges. It is n-regular. Any vertex u∈VMBnr has two neighbors in MBni and MBnj which are called the outside neighbors of u where i,j,r∈1,n and i,j,r differ from each other. Let N′u=u+,u− be the two outside neighbors of u, in which u+ and u− are the labels of u1n and un−1,n, respectively. Let F⊆VMBn be a faulty set and let Fi=F∩VMBni. Let Ft,s=Ft+Ft+1+⋯+Fs, MBnt,s=MBnVMBnt∪VMBnt+1∪⋯∪VMBns, and MBnt,s−Ft,s=MBnVMBnt−Ft∪VMBnt+1−Ft+1∪⋯∪VMBns−Fs for t,s∈1,n and t<s. When we decompose Bn into n subgraphs Bn1,Bn2,…,Bnn along the last position, where each vertex u∈VBni has a fixed integer i in the last position for i∈1,n, then Bni≅Bn−1. Similar to the above, let Bnt,s=BnVBnt∪VBnt+1∪⋯∪VBns, Bnt,s−Ft,s=BnVBnt−Ft∪VBnt+1−Ft+1∪⋯∪VBns−Fs for t,s∈1,n and t<s.The graphs ofMB3, MB4, B3, B4, and Q3 are given in Figures 1–3.Figure 1
The modified bubble-sort graphs of MB3 and MB4.Figure 2
The bubble-sort graphs ofB3 and B4.Figure 3
The hypercubeQn of n=3.Remark 1.
Figure1 is general; it can be used in a different way, e.g., article “The 2-good-neighbor diagnosability of modified bubble-sort graphs under the PMC and MM∗ model” where we studied the 2-good-neighbor diagnosability which is the maximum number of faulty vertices that the system can ensure to identify under the condition that every fault-free vertex has at least 2 fault-free neighbors.


## 2.3. The Propositions ofMBn and Bn

The automorphism group of a graphG is transitive if there exists an automorphism φ to any pair u, v of vertices in G such that φu=v. In this case, G is called vertex transitive. Note that MBn is a special Cayley graph.Proposition 1 (see [3]).
For any integern≥3, MBn is vertex transitive and bipartite.Proposition 2 (see [10]).
For any integern≥2, Bn is vertex transitive and bipartite.Proposition 3 (see [4]).
For any integern≥3, the girth of MBn is 4.Proposition 4 (see [5]).
For any two distinct verticesu and v in MBn, Nu∩Nv≤2, when uv∉EMBn; Nu∩Nv=0, when uv∈EMBn for n≥4.
The edges whose end vertices in differentMBni’s are called cross-edges. Two edges are said to be independent if they are not adjacent.Proposition 5 (see [5]).
LetMBni and MBnj be defined as above. There are exactly 2n−2! independent cross-edges between MBni and MBnj for i,j∈1,n and i≠j.Proposition 6 (see [5]).
For anyu,v∈VMBni, each of u and v has two distinct outside neighbors, u+,u−∩v+,v−=∅ for i∈1,n.Proposition 7.
For any vertexu∈VMBn1,2, u+∈VMBn3,n or u−∈VMBn3,n.Proof.
Letu∈VMBn1,2, without loss of generality, let u=u1u2…un−11∈VMBn1. By the definition of MBn, u+=1u2…un−1u1 and u−=u1u2…1un−1. Note that u1≠1, un−1≠1 and u1≠un−1. Therefore, u+ or u−∈VMBn3,n.Proposition 8 (see [5]).
For any vertexu∈VMBnr, u+∈VMBni and u−∈VMBnj, where r,i,j∈1,n and r,i,j differ from each other.Proposition 9 (see [16]).
Each vertexu∈VBni has a unique outside neighbor for i∈1,n.Proposition 10 (see [16]).
LetBni and Bnj be defined as above. There are exactly n−2! independent cross-edges between Bni and Bnj for i,j∈1,n and i≠j.Proposition 11 (see [16]).
For any two distinct verticesu and v in Bni, they have different outside neighbors for i∈1,n.Proposition 12 (see [17]).
For any two distinct verticesu and v in Bn, Nu∩Nv≤2, when uv∉EBn; Nu∩Nv=0, when uv∈EBn.Proposition 13 (see [14]).
Letv1v2v3v4v1 be a 4-cycle in Bn. Then v2=v1i,i+1, v3=v2j,j+1, v4=v3i,i+1, and v1=v4j,j+1 for i,j∈1,n and i−j>1.Proposition 14 (see [14]).
Every 6-cycle inBn is in one of the following three types:(1)
i,i+1j,j+1i,i+1j,j+1i,i+1j,j+1 for i−j=1.(2)
i,i+1k,k+1i,i+1j,j+1k,k+1j,j+1 for i and j are related, and they are both unrelated with k.(3)
i,i+1j,j+1k,k+1i,i+1j,j+1k,k+1 or i,i+1j,j+1k,k+1i,i+1k,k+1j,j+1 or i,i+1j,j+1k,k+1j,j+1i,i+1k,k+1 for i,j,andk are all mutually unrelated.Proposition 15 (see [5]).
κ2MBn=4n−8 for n≥3.Proposition 16 (see [13]).
κ1Bn=2n−4 for n≥3.Proposition 17 (see [17]).
κ2Bn=4n−3 for n≥3.Proposition 18 (see [14]).
κ3B5=12; κ3Bn=8n−32 for n≥6.Proposition 19 (see [12]).
κBn=n−1.Proposition 20 (see [7]).
For a graphG=V,E, κG≤δG.Proposition 21.
κMBn=n.Proof.
SinceMB3≅K3,3 by Figure 1, we have κMB3=3. We will prove κMBn=n when n≥4. Note that MBn is n-regular. So, δMBn=n. Combining this with Proposition 20, we have that κMBn≤δMBn=n. Let F⊆VMBn and F≤n−1. For the purpose of proving κMBn≥n, it is sufficient to prove that MBn−F is connected when F≤n−1. We decompose MBn along the last position, denoted by MBni for i∈1,n. Note that MBni≅Bn−1 for i∈1,n. Let Fi=F∩VMBni and F1=maxFi:1≤i≤n for i∈1,n.Case 1.F1<n−2.Note thatMBni≅Bn−1. We have κMBni=n−2 by Proposition 19. Combining this with F1=maxFi:1≤i≤n, we have that MBni−Fi is connected for i∈1,n. By Proposition 5, there are 2n−2! independent cross-edges between two different MBni’s and 2n−2!>n−1 for n≥4, and we have that MBnVMBni−Fi∪VMBnj−Fj is connected for i,j∈1,n and i≠j. Thus, MBn−F is connected.Case 2.n−2≤F1≤n−1.In this case,F2,n≤1. By Proposition 19, MBnj−Fj is connected for j∈2,n. Since 2n−2!>1≥Fr+Fs for r,s∈2,n and r≠s, we have that MBnVMBnr−Fr∪VMBns−Fs is connected by Proposition 5. Thus, MBn2,n−F2,n is connected. By Proposition 8, each vertex u∈VMBn1−F1 has at least one outside neighbor in MBn2,n−F2,n. Thus, MBn−F is connected.
By Cases 1 and 2,F is not a cut of MBn for F≤n−1. So, κMBn≥n. Combining this with κMBn≤n, we have κMBn=n.


## 3. The 3-Good-Neighbor Connectivity of the Modified Bubble-Sort Graph

In this section, we will give the 3-good-neighbor connectivity of the modified bubble-sort graph.Lemma 1.
Letn≥4. There are no two 6-cycles with four common edges as a subgraph in Bn (Figure 4).Figure 4
Forbidden subgraph.Proof.
LetC1=u1u2u3y3xy1u1 and C2=u1u2u3y3xy2u1 be two 6-cycles (Figure 4). Obviously, C1 and C2 have four common edges. Every 6-cycle in Bn has three types by Proposition 14. Without loss of generality, we suppose that C1 is the first type in Proposition 14; furthermore, we let u1=1 and C1 is the type of 122312231223. Then u2=u112,u3=u223,y3=u312,x=y323,y1=x12,andu1=y123. Therefore, we have u12312=u1132=x. Note the fact that 132=2312=1213=1323. There are three different 2-path’s from u1 to x. However, there is no edge corresponding to the transposition (13) by the definition of Bn. Therefore, there is only one 2-path from x to u1. Then C1 and C2 cannot exit at the same time. When C1 is the other type in Proposition 14, similarly, we have Figure 4 is a forbidden subgraph.Lemma 2 (see [18]).
Letn≥4 and F⊆VBn with F≤2n−5. If Bn−F is disconnected, then Bn−F has two components, one of which is an isolated vertex.Lemma 3.
LetF⊆VB5 with F≤7. If B5−F is disconnected, then B5−F satisfies one of the following conditions:(1)
B5−F has two components, one of which is an isolated vertex.(2)
B5−F has two components, one of which is a K2.(3)
B5−F has two components, one of which is a 2-path.(4)
B5−F has three components, two of which are isolated vertices.Proof.
WhenB5−F is disconnected, we have F≥4 by Proposition 19. So, 4≤F≤7. We decompose B5 along the last position, denoted by B5i for i∈1,5. Note that B5i≅B4. Let Fi=F∩VB5i and F1=maxFi:1≤i≤5 for i∈1,5. When B5i−Fi is disconnected, let the maximum connected component of it be Ci for i∈1,5.Claim 1. IfFi<3 and Fj<3, then B5VB5i−Fi∪VB5j−Fj is connected for i,j∈1,5 and i≠j.Note thatκB5i=3 by Proposition 19. So, B5i−Fi is connected when Fi<3 for i∈1,5. Since 5−2!=6>4≥Fi+Fj for i,j∈1,5 and i≠j, we have that B5VB5i−Fi∪VB5j−Fj is connected by Proposition 10.Claim 2.3≤F1≤6.IfF1<3, then Fi<3 for i∈1,5. B5VB5i−Fi∪VB5j−Fj is connected by Claim 1 for i,j∈1,5 and i≠j. Then B5−F is connected, a contradiction to that B5−F is disconnected. So, F1≥3. If F1=7, then F2,5=0. B52,5 is connected by Claim 1. By Proposition 9, each vertex in B51−F1 has one outside neighbor; we have that B51−F1 is connected to B52,5. So, B5−F is connected, a contradiction to that B5−F is disconnected. Therefore, 3≤F1≤6.Case 1.F1=3.Suppose thatFi<3 for i∈2,5. By Claim 1, we have that B5VB5i−Fi∪VB5j−Fj is connected for i∈2,5. Therefore, B52,5−F2,5 is connected. Suppose that B51−F1 is connected. Since 5−2!=6>5≥F1+F2, we have that B5VB51−F1∪VB52−F2 is connected by Proposition 10. Thus, B5−F is connected, a contradiction to that B5−F is disconnected. Then B51−F1 is disconnected. By Lemma 2, B51−F1 has two components, one of which is an isolated vertex v1. Note that F2,5≤F−F1≤7−3=4. Since VB51−F1−1=24−3−1=20=VC1>4≥F2,5, we have B5VC1∪VB52,5−F2,5 is connected by Proposition 9. When B5−F is disconnected, it has two components, one of which is an isolated vertex v1.SinceF≤7, there is only one Fi that can satisfy Fi=3 for i∈2,5. Without loss of generality, let F2=3. Then F3,5≤1. By Claim 1, we have that B5VB5i−Fi∪VB5j−Fj is connected for i∈3,5. Therefore, B53,5−F3,5 is connected. Suppose that both B51−F1 and B52−F2 are connected. Note that F1=F2=3. Since 5−2!=6>4≥Fi+F5, we have that B5VB5i−Fi∪VB53,5−F3,5 is connected by Proposition 10 for i=1,2. Thus, B5−F is connected, a contradiction to that B5−F is disconnected. When one of B51−F1 and B52−F2 is disconnected, similar to the above, B5−F has two components, one of which is an isolated vertex. Suppose that B51−F1 is disconnected and B52−F2 is disconnected. By Lemma 2, both of them have two components, one of which is an isolated vertex. Since F3,5≤1, we have F5≤1. Combining this with the isolated vertex in B51−F1 or B52−F2 may have an outside neighbor in F5, and the cross-edges that can be broken between B5i−Fi and B55−F5 have to be added by 1 for i=1,2. Then 5−2!=6>5=3+1+1≥Fi+1+F5; and we have that B5VCi∪VB53,5−F3,5 is connected by Proposition 10 for i=1,2. Therefore, B5VC1∪VC2∪VB53,5−F3,5 is connected. When B5−F is disconnected, it may have an isolated vertex, a K2 or two isolated vertices as its components.Case 2.F1=4.Suppose thatFi<3 for i∈2,5. Then F2,5≤3. By Claim 1, we have that B52,5−F2,5 is connected. Suppose that B51−F1 is connected. By Proposition 9, each vertex u∈VB51−F1 has one outside neighbor in B52,5−F2,5. Thus, B5−F is connected, a contradiction to that B5−F is disconnected. Then B51−F1 is disconnected. Note that B51≅B4 and F1=4. Combining these with Figure 2, B51−F1−VC1 may have five cases: (1) one isolated vertex; (2) two isolated vertices; (3) a 2-path; (4) a K2; and (5) a 4-cycle. Since VC1≥VB4−F1−4=24−4−4=16>3≥F2,5, we have that B5VC1∪VB52,5−F2,5 is connected by Proposition 9. If the 4-cycle is a component of B5−F, then each vertex of it has an outside neighbor in F2,5 by Proposition 9. Combining this with F2,5≤3, the 4-cycle cannot be a component of B5−F. When B5−F is disconnected, B5−F may have one isolated vertex, two isolated vertices, a 2-path, or a K2 as its component.SinceF≤7, there is only one Fi that can satisfy Fi=3 for i∈2,5. Without loss of generality, let F2=3. Then F3,5=0. By Claim 1, we have that B53,5 is connected. Suppose that both B51−F1 and B52−F2 are connected. Since 5−2!=6>4=4+0≥F1+F5 and 5−2!=6>3=3+0≥F2+F5, we have that B5VB51−F1∪VB53,5 is connected and B5VB52−F2∪VB53,5 is connected by Proposition 10. Thus, B5−F is connected, a contradiction to that B5−F is disconnected. So, at least one of B51−F1 and B52−F2 is disconnected. Suppose that B51−F1 is connected and B52−F2 is disconnected. By Lemma 2, B52−F2 has two components, one of which is an isolated vertex. Since 5−2!=6>4=4+0=F1+F5 and 5−2!=6>4=3+1+0=F2+1+F5, we have that B5VB51−F1∪VC2∪VB53,5 is connected by Proposition 10. Note that F1+F3,5=4. When B5−F is disconnected, it has two components, one of which is an isolated vertex. Suppose that B52−F2 is connected and B51−F1 is disconnected. By Proposition 10, there are 5−2!=6 cross-edges between B52−F2 and B53, so B52,5−F2,5 is connected. Note that F2,5≤F−F1≤7−4=3. Since VC1≥VB4−F1−4≥24−4−4=16>3≥F2,5, we have that B5VC1∪VB52,5−F2,5 is connected by Proposition 9. The same as above, B51−F1−VC1 may have five cases. Now we discuss the conditions of B51−F1−VC1 one by one. When B51−F1−VC1 is one isolated vertex v1, v1 can be the isolated vertex of B5−F. When B51−F1−VC1 are two isolated vertices v1 and v3, v1 and v3 must be in a 4-cycle v1v2v3v4v1 (see Figure 2), and they are not adjacent. Otherwise, if v1 and v3 are not in the 4-cycle, then F1≥5 by Proposition 19, a contradiction to that F1=4. By Proposition 13, the 4-cycle is the form of v1,v2=v112,v3=v234,v4=v312. Obviously, the forth position of v1 and v3 are different. So, the outside neighbors of v1 and v3 are in different B5i’s for i∈2,5. Note that F3,5=0. Then only one of v1 and v3 can be the component of B5−F. When B51−F1−VC1 is a 2-path with vertices v1, v2, v3 in this order, v1v2v3 must be in a 4-cycle by Proposition 19. Otherwise, if v1v2v3 is not in a 4-cycle, then F1=5, a contradiction to that F1=4. The outside neighbors of the 2-path are in different B5i’s for i∈2,5. So, the 2-path cannot be the component of B5−F. When B51−F1−VC1 is a K2, the outside neighbors of the K2 can be in one copy of B5i for i∈2,5. Therefore, the K2 can be a component of B5−F. When B51−F1−VC1 is a 4-cycle, combining Proposition 13 with the proof above, the outside neighbors of the 4-cycle are in different B5i’s for i∈2,5. Therefore, the 4-cycle cannot be a component of B5−F. By the proof above, B5−F may have one isolated vertex or a K2 as a component. Suppose that B51−F1 is disconnected and B52−F2 is disconnected. Note that B51−F1−VC1 may have five cases, but only one isolated vertex or a K2 can be a component of B5−F. By Lemma 2, B52−F2 has one isolated vertex u1 and a connected component C2. Since VC1≥VB4−F1−4≥24−4−4=16>0=F3,5 and 5−2!=6>4=3+1+0=F2+1+F5, we have that B5VC1∪VC2∪VB53,5−F3,5 is connected by Propositions 9 and 10. If B51−F1−VC1 is an isolated vertex v1, then B5−F may have one isolated vertex, two isolated vertices, or a K2=v1u1 as its component. If B51−F1−VC1 is a K2=v1v2, we first consider the case that the K2 is not a component of B5−F, then only u1 can be a component of B5−F. Suppose that K2=v1v2 is a component of B5−F. Since F3,5=0, K2=v1v2 must have two outside neighbors v1− and v2− in F2. Otherwise, if v1− and v2− are not in F2, then K2 is not a component of B5−F. Note that v1−v2− is a K2. Combining F2=3 with κB4=3, we have NB52u1=F2. Since there is no triangle in B5 by Proposition 2, only one of v1− and v2− is connected to u1. Then F2≥4, a contradiction to that F2=3. So, one of v1 and v2 is connected to u1. The K2=v1v2 cannot be a component of B5−F under this condition. Therefore, B5−F may have a 2-path as its component.Case 3.F1=5.In this case,F2,5≤2. By Claim 1, we have that B52,5−F2,5 is connected. Suppose that B51−F1 is connected. By Proposition 9, each vertex u∈VB51−F1 has one outside neighbor in B52,5−F2,5. Thus, B5−F is connected, a contradiction to that B5−F is disconnected. Then B51−F1 is disconnected. Several conditions may occur in B51−F1 (see Figure 2). Note that F2,5≤2. B5−F may have an isolated vertex, a K2, or two isolated vertices as its components by Proposition 9.Case 4.F1=6.In this case,F2,5≤1. By Claim 1, we have that B52,5−F2,5 is connected. By Case 3, B51−F1 is disconnected. Several conditions may occur in B51−F1 (see Figure 2). Note that F2,5≤1. So, only one vertex can be isolated in B51−F1 by Proposition 9. So, B5−F have one isolated vertex and a connected component.
By Cases 1–4, whenB5−F is disconnected with F≤7, it may have 4 conditions as above. □Lemma 4.
LetF⊆VB6 with F≤11. If B6−F is disconnected, then B6−F satisfies one of the following conditions:(1)
B6−F has two components, one of which is an isolated vertex.(2)
B6−F has two components, one of which is a K2.(3)
B6−F has two components, one of which is a 2-path.(4)
B6−F has three components, two of which are isolated vertices.(5)
B6−F has three components, one of which is an isolated vertex, the second one is a K2, and the last one is a connected component.(6)
B6−F has four components, three of which are isolated vertices.(7)
B6−F has two components, one of which is a star with four vertices.Proof.
WhenB6−F is disconnected, we have F≥5 by Proposition 19. So, 5≤F≤11. We decompose B6 along the last position, denoted by B6i for i∈1,6. Note that B6i≅B5. Let Fi=F∩VB6i for i∈1,6 and F1=maxFi:1≤i≤6 for i∈1,6. When B6i−Fi is disconnected, let the maximum connected component of it be Ci for i∈1,6.Claim 1. IfFi<4 and Fj<4, then B6VB6i−Fi∪VB6j−Fj is connected for i,j∈1,6 and i≠j.Note thatκB6i=4 by Proposition 19. So, B6i−Fi is connected when Fi<4 for i∈1,6. Since 6−2!=24>8>Fi+Fj for i,j∈1,6 and i≠j, we have that B6VB6i−Fi∪VB6j−Fj is connected by Proposition 10.Claim 2.4≤F1≤10.IfF1<4, then Fi<4 for i∈1,6. By Claim 1, we have that B6VB6i−Fi∪VB6j−Fj is connected. Therefore, B6−F is connected, a contradiction to that B6−F is disconnected. So, F1≥4. If F1=11, then F2,6=0. B62,6 is connected by Claim 1. By Proposition 9, each vertex in B61−F1 has one outside neighbor in B62,6, and we have that B6−F is connected, a contradiction to that B6−F is disconnected. Therefore, 4≤F1≤10.Case 1.4≤F1≤7.Suppose thatFi<4 for i∈2,6. By Claim 1, we have that B6VB6i−Fi∪VB6j−Fj is connected. Therefore, B62,6−F2,6 is connected. Suppose that B61−F1 is connected. Since 6−2!=24>11≥F1+F2,6, we have that B6−F is connected by Proposition 10, a contradiction to that B6−F is disconnected. Then B61−F1 is disconnected. By Lemma 3, B61−F1−VC1 has four conditions. Each condition of the small component has vertices not exceeding 3. Note that F2,6≤F−F1min≤11−4=7. Since VC1≥VB5−F1−3=5!−7−3>7≥F2,6, we have that B6VC1∪VB62,6−F2,6 is connected by Proposition 9. When B6−F is disconnected, it may have one isolated vertex, two isolated vertices, a K2, or a 2-path as its component.Since4≤F≤11, there is only one Fi that can satisfy Fi≥4 for i∈2,6. Without loss of generality, we suppose that F2≥4. Then Fj<4 for j∈3,6 and F3,6≤3. By Claim 1, B63,6−F3,6 is connected. If F2>5, then F≥F1+F2≥2×6=12, a contradiction to that F≤11. So, F2=4,5. Suppose that both B61−F1 and B62−F2 are connected. Since 6−2!=24>11≥F1+F2, we have that B61,2−F1,2 is connected by Proposition 10. Meanwhile, 6−2!=24>7≥F1+F3, and we have that B6VB61−F1∪VB63,6−F3,6 is connected, too. So, B6−F is connected, a contradiction to that B6−F is disconnected. Suppose that B61−F1 is connected and B62−F2 is disconnected. B6VB61−F1∪VB63,6−F3,6 is connected by Proposition 10. B62−F2 has only one isolated vertex v2 and a connected component C2 by Lemma 2. Since 6−2!=24>8≥F2+F3+1, B6VB61−F1∪VC2∪VB63,6−F3,6 is connected by Proposition 10. v2 can be the only isolated vertex of B6−F. Suppose that B61−F1 is disconnected and B62−F2 is connected, and this is same as above. Suppose that B61−F1 is disconnected and B62−F2 is disconnected, by Lemmas 2 and 3, B61−F1 has four conditions and B62−F2 has only one isolated vertex v2. Combining Proposition 10 with the proof above, we have B6VC1∪VC2∪VB63,6−F3,6 is connected. We will discuss the conditions of B61−F1 one by one. When B61−F1 has an isolated vertex u1, note that B62−F2 has only one isolated vertex. Then B6−F may have one isolated vertex, two isolated vertices, or a K2 as its component. When B61−F1 has a K2, F1=6,7 by Proposition 16. Then 4≤F2≤5,F3,6≤1. B6−F may have one isolated vertex, a K2, a 2-path, or a K2 and one isolated vertex as its components. When B61−F1 has a 2-path with vertices u1,u2,u3 in this order, since κB5=4 by Proposition 19, we have F1=7 and the 2-path must be in a 4-cycle. Otherwise, if the 2-path is not in a 4-cycle, then F1=8 and F2=3, a contradiction to that 4≤F1≤11 and F2≥4. So, F2=4. By Proposition 13, the 4-cycle in B61−F1 has two forms. Without loss of generality, we first let the 4-cycle be the form of u1=x1x2x3x4x51,u2=u112=x2x1x3x4x51,u3=u245=x2x1x3x5x41,u4=u312=x1x2x3x5x41, where x1,x2,x3,x4,x5∈2,6 and they differ from each other. Obviously, the 2-path from this 4-cycle has outside neighbors in different B6i’s for i∈2,6. Note that F3,6=0, and the 2-path cannot be a component of B6−F. Secondly, we let the 4-cycle be the form of u1=x1x2x3x4x51,u2=u112=x2x1x3x4x51,u3=u234=x2x1x4x3x51,u4=u312=x1x2x4x3x51, where x1,x2,x3,x4,x5∈2,6 and they differ from each other. If the 2-path u1u2u3 is a component of B6−F, then it must have three outside neighbors u1−,u2−,u3−⊆F2. Otherwise, it is not a component of B6−F. Furthermore, u1−u2−u3− is a 2-path with vertices in this order. Note that F2=4 and v2 is an isolated vertex of B62−F2, and we have NB62v2=F2. Since there is no triangle in B6 by Proposition 2, we have that u1− and u3− are connected to v2 and u2−=v2. Therefore, B6−F may have one isolated vertex or a star with four vertices as its component. When B61−F1 has two isolated vertices u1 and u1′. Note that κB5=4 by Proposition 19, and we have F1≥6. Then F2≤5, F3,6≤1. B6−F may have one isolated vertex, two isolated vertices, three isolated vertices, a K2 or a K2 and one isolated vertex as its components.Case 2.8≤F1≤10.In this case,F2,6≤3. By Claim 1, B62,6−F2,6 is connected. Suppose that B61−F1 is connected. Since 6−2!=24>11=F≥F1+F2, we have that B6−F is connected by Proposition 10, a contradiction to that B6−F is disconnected. Then B61−F1 is disconnected. Combining Proposition 9 with F2,6≤3, the component of B6−F has at most three vertices. So, B6−F may have one isolated vertex, two isolated vertices, three isolated vertices, a K2, a 2-path, or a K2 with one isolated vertex as its components.
By Cases 1 and 2, whenB6−F is disconnected with F≤11, it may have 7 conditions as above.Lemma 5.
Letn≥6 and F⊆VBn with F≤4n−13. If Bn−F is disconnected, then Bn−F satisfies one of the following conditions:(1)
Bn−F has two components, one of which is an isolated vertex, and F≥n−1.(2)
Bn−F has two components, one of which is a K2, and F≥2n−4.(3)
Bn−F has two components, one of which is a 2-path, and F≥3n−8.(4)
Bn−F has three components, two of which are isolated vertices, and F≥2n−4.(5)
Bn−F has three components, one of which is an isolated vertex, the second one is a K2, and the last one is a connected component, and F≥3n−6.(6)
Bn−F has four components, three of which are isolated vertices, and F≥3n−7.(7)
Bn−F has two components, one of which is a star with four vertices, and F≥4n−13.Proof.
By Lemma4, the result holds for n=6. We proceed by induction on n. Assume n≥7 and the result holds for Bn−1. By Proposition 19, F≥n−1. We decompose Bn along the last position, denoted by Bni for i∈1,n. Note that Bni≅Bn−1. Let Fi=F∩VBni for i∈1,n and F1=maxFi:1≤i≤n. When Bni−Fi is disconnected, let the maximum connected component of it be Ci for i∈1,n.Claim 1. IfFi<n−2 and Fj<n−2, then BnVBni−Fi∪VBnj−Fj is connected for i,j∈1,n and i≠j.
Note thatκBni=n−2 by Proposition 19. When Fi<n−2, Bni−Fi is connected for i∈1,n. Since n−2!>2n−2>Fi+Fj, we have that BnVBni−Fi∪VBnj−Fj is connected by Proposition 10 for i,j∈1,n and i≠j.Case 1.F1<n−2.SinceF1=maxFi:1≤i≤n, Fi<n−2 for i∈1,n. Note that BnVBni−Fi∪VBnj−Fj is connected by Claim 1 for i,j∈1,n. Then Bn−F is connected, a contradiction to that Bn−F is disconnected.Case 2.n−2≤F1≤2n−7.Suppose thatFi<n−2 for i∈2,n. Note that BnVBni−Fi∪VBnj−Fj is connected by Claim 1 for i,j∈2,n. Then Bn2,n−F2,n is connected. Suppose that Bn1−F1 is connected. Since n−2!>3n−9=2n−7+n−2>F1+Fi for i∈2,n, we have that Bn−F is connected by Proposition 10, a contradiction to that Bn−F is disconnected. Then Bn1−F1 is disconnected. By Lemma 2, Bn1−F1 has two components, one of which is an isolated vertex u1, and the other one is C1. Since n−2!>3n−8=2n−7+n−2+1>F1+F2+1, we have that BnVC1∪VBn2,n−F2,n is connected by Proposition 10. Therefore, u1 can be the isolated vertex of Bn−F. By Proposition 9, u1 has an outside neighbor in F2,n, so F≥F1+1≥n−1.Suppose that there is only oneFi that satisfies Fi≥n−2 for i∈2,n. Without loss of generality, we suppose that i=2. Then n−2≤F2≤2n−7 and Fj<n−2 for j∈3,n. By Claim 1, Bn3,n−F3,n is connected. Suppose that both Bn1−F1 and Bn2−F2 are connected. Since n−2!>22n−7≥F1+F2>3n−9=2n−7+n−2>F1+Fn, we have that Bn−F is connected by Proposition 10, a contradiction to that Bn−F is disconnected. When one of Bn1−F1 and Bn2−F2 is disconnected, this is same as above. When Bn1−F1 is disconnected and Bn2−F2 is disconnected, by Lemma 2, Bni−Fi has two components, one of which is an isolated vertex ui, and the other component is Ci for i∈1,2. Note that n−2≤Fi≤2n−7 for i=1,2. Since n−2!>3n−8=2n−7+n−2+1>Fi+Fj+1 for i=1,2 and j∈3,n, we have that BnVC1∪VC2∪VBn3,n−F3,n is connected by Proposition 10. Since F1+F3,n≥n−2 and F2,n≥n−2, Bn−F may have one isolated vertex, two isolated vertices, or a K2=u1u2 as its component. Furthermore, when a K2=u1u2 is the component of Bn−F, combining this with Proposition 9, u1 is the outside neighbor of u2. So, F≥F1+F2≥2n−4. When u1 and u2 are two isolated vertices of Bn−F, the outside neighbor of u1 can be in F2, and the outside neighbor of u2 can be in F1. So,F≥F1+F2≥2n−4.Suppose that there are twoFi′s that satisfy Fi≥n−2 for i∈2,n. Without loss of generality, we suppose that i=2,3. Then Fj<n−2 for j∈4,n. By Claim 1, Bn4,n−F4,n is connected. Since F≤4n−13, we have that n−2≤Fi≤2n−9 for i∈1,3. When one or two of Bni−Fi are disconnected, this is same as above for i∈1,3. So, we discuss none of Bni−Fi is connected for i∈1,3. By Lemma 2, each of Bni−Fi has two components, one of which is an isolated vertex ui for i∈1,3. Since n−2!>4n−16=22n−9+2≥F1+F2+2 and n−2!>3n−10=2n−9+n−2+1>F1+Fn+1 for i,j∈1,3, we have that BnVC1∪VC2∪VC3∪VBn4,n−F4,n is connected by Proposition 10. If all of ui’s are connected to BnVC1∪VC2∪VC3∪VBn4,n−F4,n for i∈1,3, then Bn−F is connected, a contradiction to that Bn−F is disconnected. If one of ui’s is an isolated vertex of Bn−F, we first discuss the other two of ui’s are connected to BnVC1∪VC2∪VC3∪VBn4,n−F4,n, F≥Fi+1≥n−1 for i∈1,3. Then we discuss that u1 and u2 comprise a component K2=u1u2 of Bn−F. By Proposition 9, u3 has at most one common neighbor with u1 or u2 in F. Combining this with κBn=n−1, we have that F≥3n−2=3n−6. If u1 and u2 are the components of Bn−F, then F≥2F1≥2n−4. If all of ui’s are the components of Bn−F, then we have to consider the case that they use the least number of vertices in F for i∈1,3. Combining Lemma 1 with Propositions 12 and 19, we have F≥n−1−2+n−1−4+n−1−2+4=3n−7. However, u1u2u3 cannot comprise a 2-path of Bn−F by Proposition 9. Therefore, Bn−F may have one isolated vertex, two isolated vertices, three isolated vertices, a K2, or a K2 with an isolated vertex as its components.Case 3.2n−6≤F1≤4n−17.Suppose thatFi<n−2 for i∈2,n. By Claim 1, Bn2,n−F2,n is connected. Suppose that Bn1−F1 is connected. Since n−2!>4n−13≥F1+F2 by Proposition 10, we have that Bn−F is connected, a contradiction to that Bn−F is disconnected. Then Bn1−F1 is disconnected. Note that Bn1≅Bn−1. Bn1−F1 has seven conditions by the hypothesis and each small component of Bn1−F1 with vertices not exceeding 4. Since VBn−1−F1−4=n−1!−F1−4>4n−13−F1−4=F−F1−4 when n≥6, we have that BnVC1∪VBn2,n−F2,n is connected by Proposition 9. Since 2n−6≤F1≤4n−17, we have that 4≤F2,n≤2n−7. Combining 4≤F2,n≤2n−7 with the conditions of Bn1−F1, all of the conditions in Bn1−F1 will be hold in Bn−F. Furthermore, when Bn1−F1 has a 2-path with vertices u1, u2, u3 in this order, by Proposition 19, F1≥3n−11. We have F1=3n−11 if and only if u1, u2 and u3 are in a 4-cycle. So, F≥F1+3≥3n−11+3=3n−8 by Proposition 9. When Bn1−F1 has a star with four vertices u1, u2, u3, and u4 (see Figure 3.), without loss of generality, let u1=u1, u2=v1, u3=v2, and u4=v4 in Figure 3. Obviously, the vertices in the star have three common neighbors. Combining this with κBn−1=n−2, we have that F1≥4n−5+3=4n−17. F1=4n−17 if and only if ui’s are in a Q3 for i∈1,4. So, F≥F1+4≥4n−17+4=4n−13 by Proposition 9.SinceF≤4n−13, there is only one Fi that can satisfy Fi≥n−2 for i∈2,n. Without loss of generality, we suppose that i=2. In this case, 2n−6≤F1≤F−F2min≤3n−11, n−2≤F2≤F−F1min≤2n−7, F3,n≤F−F1min−F2min≤n−5. By Claim 1, Bn3,n−F3,n is connected. Suppose that both Bn1−F1 and Bn2−F2 are connected. Then Bn−F is connected by Proposition 10, a contradiction to that Bn−F is disconnected. Suppose that Bn2−F2 is connected and Bn1−F1 is disconnected. By the proof above, BnVC1∪VBn2,n−F2,n is connected. By the hypothesis, Bn1−F1 has seven conditions, and we discuss them one by one. When Bn1−F1 has an isolated vertex u1 or a K2, note that F3,n≤n−5, u1 or the K2 can be the component of Bn−F. When Bn1−F1 has a 2-path with vertices u1, u2, u3 in this order, F1≥3n−11 by Propositions 12 and 19. Note that 2n−6≤F1≤3n−11. We have that F1=3n−11, F2=n−2, and F3,n=0. Furthermore, u1u2u3 is in a 4-cycle. The 4-cycle is the form in Proposition 13. Based on the discussion of Case 1 in Lemma 4, the 2-path can be a component of Bn−F for n=6. So, the 2-path u1u2u3 can be a component of Bn−F for n≥6 and F≥F1+3≥3n−8. When Bn1−F1 has two isolated vertices u1 and u1′, F1≥2n−6 by Case 2. F1=2n−6 if and only if u1 and u1′ are not adjacent in a 4-cycle. So, u1 and u1′ can be the components of Bn−F and F≥F1+2≥2n−4. When Bn1−F1 has a K2 and an isolated vertex u1, F1≥3n−1−7=3n−10 by Case 2. Note that F1≤3n−11<3n−10, which is a contradiction. When Bn1−F1 has three isolated vertices, F1≥3n−1−7=3n−10 by Case 2. Note that 2n−6≤F1≤3n−11<3n−10, which is a contradiction. When Bn1−F1 has a star with 4 vertices, F1≥4n−1−13=4n−17 by the proof above. The star is in a Q3 when F1=4n−17. Combining F1≤3n−11 with F1≥4n−17, we have that there is a star if and only if n=6. Note that F1=3n−11=3×6−11=7, F2=6−2=4, and F3,6=0. Since the star is in a Q3, any two vertices of the star are in a 4-cycle. Then the outside neighbors of the star are in different B6i’s for i∈2,6 by Proposition 13. So, the star cannot be a component of Bn−F. Under this condition, Bn−F may have an isolated vertex, two isolated vertices, a K2, or a 2-path as its component. Suppose that Bn1−F1 is connected and Bn2−F2 is disconnected. By Lemma 2, Bn2−F2 has only one isolated vertex v2. By the proof above, BnVBn1−F1∪VBn3,n−F3,n is connected. Since n−2!>5n−17=3n−11+2n−7+1≥F1+F2+1, we have that BnVBn1−F1∪VC2∪VBn3,n−F3,n is connected. v2 can be the isolated vertex of Bn−F and F≥n−1. Suppose that Bn1−F1 is disconnected and Bn2−F2 is disconnected. By the proof above, BnVC1∪VC2∪VBn3,n−F3,n is connected. Note that Bn2−F2 has only one isolated vertex v2 and a connected component C2. When Bn1−F1 is disconnected, it has four conditions by the proof above, and we discuss them one by one. When Bn1−F1 has an isolated vertex u1, Bn−F may have one isolated vertex, two isolated vertices, or a K2=u1v2 as its component. When Bn1−F1 has a K2=u1u2, Bn−F may have one isolated vertex, a K2=u1u2, a K2=u1u2 with an isolated vertex v2, or a 2-path u1u2v2 as its component. When Bn1−F1 has a 2-path with vertices u1, u2, u3 in this order, by the proof above, F1=3n−11, F2=n−2, and F3,n=0. Under this condition, the 2-path u1u2u3 can be a component of Bn−F if and only if their outside neighbors are u1−,u2−,u3−⊆F2. Furthermore, u1−,u2−,u3− is a 2-path with vertices in this order. Note that F2=n−2 and v2 is an isolated vertex of Bn2−F2. So, NBn2v2=F2. Since there is no triangle in Bn by Proposition 2, u1− and u3− are connected to v2 and u2−=v2. Therefore, Bn−F may have one isolated vertex or a star with four vertices as its component. When Bn1−F1 has two isolated vertices u1 and u1′, Bn−F may have one isolated vertex, a K2=u1v2, a K2=u1v2 with an isolated vertex u2, or three isolated vertices u1,u2,v2 as its components. Therefore, Bn−F may have one isolated vertex, two isolated vertices, a K2, a K2 with an isolated vertex, a 2-path, or a star with four vertices as its component.Case 4.4n−16≤F1≤4n−13.In this case,F2,n≤3. By Claim 1, Bn2,n−F2,n is connected. Suppose that Bn1−F1 is connected. Since n−2!>4n−13≥F1+Fi for i∈2,n, we have that Bn−F is connected by Proposition 10, a contradiction to that Bn−F is disconnected. Then Bn1−F1 is disconnected. Whether what happens in Bn1−F1, combining Proposition 9 with F2,n≤3, Bn−F may have one isolated vertex, two isolated vertices, three isolated vertices, a K2 and an isolated vertex, a 2-path, or a K2 as its component.Lemma 6.
Letn≥6 and F⊆VMBn. If F is a 3-good-neighbor cut of MBn, then F≥8n−3.Proof.
Suppose, on the contrary, thatF is a 3-good-neighbor cut of MBn such that F≤8n−25. We decompose MBn along the last position, denoted by MBni for i∈1,n. Note that MBni≅Bn−1. Let Fi=F∩VMBni and F1=maxFi:1≤i≤n for i=1,n. If MBni−Fi is disconnected, let the maximum connected component of it be Ci for i∈1,n. Let Di be the component of MBni−Fi−VCi which corresponds to one of the seven conditions in Lemma 5 for i∈1,n.Claim 1. LetMBni, F and Fi be defined as above for i∈1,n. If there is an isolated vertex u∈VMBni−Fi for i∈1,n, then F is not a 3-good-neighbor cut of MBn.Ifu is a component of MBn−F, then it does not satisfy the definition of 3-good-neighbor. If u is connected to another component of MBn−F, note that du≤2 by Proposition 6, then u does not satisfy the definition of 3-good-neighbor. Therefore, F is not a 3-good-neighbor cut of MBn.Claim 2. IfE is a component of MBn−F with VE≤7, then E does not satisfy the definition of 3-good-neighbor.MBn is a bipartite graph by Proposition 1. Note that E is a part of vertices and edges from MBn. Then E is also a bipartite graph. Let E=X,Y. If E satisfies the definition of 3-good-neighbor, then any vertex u∈VE must have at least 3 neighbors in E. So, 4≤VE≤7. If VE=4, then there are odd cycles in MBn, a contradiction to Proposition 1. If VE=5, at least one of X and Y has no more than 2 vertices by the definition of bipartite graph, then it does not satisfy the definition of 3-good-neighbor. If VE=6,7, we first consider the case that one of X and Y has no more than 2 vertices, and the same as above we have that E does not satisfy the definition of 3-good-neighbor. Then we consider the case that both X and Y have at least 3 vertices. There are two conditions: X=3, Y=3 and X=3, Y=4. Note that each vertex in Y must have at least 3 neighbors in X to satisfy the definition of 3-good-neighbor. Any two vertices in Y have three common neighbors in X, a contradiction to Proposition 4. Therefore, E does not satisfy the definition of 3-good-neighbor.Case 1.F1<n−2.Note thatMBni≅Bn−1 and κBn−1=n−2 by Proposition 19. MBni−Fi is connected for i∈1,n. Since 2n−2!>2n−2>Fi+Fj, we have that MBnVMBni−Fi∪VMBnj−Fj is connected by Proposition 5 for i,j∈1,n. Then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn.Case 2.n−2≤F1≤2n−7.In this case, there are at most sixFi′s that can satisfy n−2≤Fi≤2n−7 for i∈2,n. Without loss of generality, we suppose that i∈2,7. Then Fj<n−2 for j∈8,n. By Case 1, MBn8,n−F8,n is connected. We consider the case that all of MBni−Fi are disconnected for i∈1,7. By Lemma 2, each of MBni−Fi has an isolated vertex vi and a connected component Ci for i∈1,7. Since 2n−2!>4n−12=22n−7+2≥Fi+Fj+2 and 2n−2!>3n−9=2n−7+n−2>Fi+F8, we have that MBnVCi∪VCj is connected and MBnVCi∪VMBn8−F8 is connected by Proposition 5 for i,j∈1,7. Therefore, MBnVC1∪⋯∪VC7∪VMBn8,n−F8,n is connected. By Claim 1, F is not a 3-good-neighbor cut of MBn, a contradiction.Case 3.2n−6≤F1≤4n−17.Suppose thatFi<n−2 for i∈2,n. By Case 1, MBn2,n−F2,n is connected. Suppose that MBn1−F1 is connected. Since 2n−2!>5n−19=4n−17+n−2>F1+F2, we have that MBn−F is connected by Proposition 5, a contradiction to that F is a 3-good-neighbor cut of MBn. Therefore, MBn1−F1 is disconnected. MBn1−F1 has seven conditions by Lemma 5. Each condition of D1 satisfies VD1≤4. Since 2n−2!>5n−15=5n−19+4>F1+F2+4, we have that MBnVC1∪VMBn2,n−F2,n is connected by Proposition 5. By Claim 1, we only need to consider the case that there is no isolated vertex in D1. So, D1 may be a K2, a 2-path, or a star with four vertices. If D1 is connected to MBn2,n−F2,n, then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. If D1 is a component of MBn−F, then each condition of D1 does not satisfy the definition of 3-good-neighbor. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Note thatF≤8n−25 and 2n−6≤F1≤4n−17. There are at most five Fi′s that can satisfy n−2≤Fi≤2n−7 for i∈2,n. If MBni−Fi is disconnected for i∈2,n, then it has one isolated vertex by Lemma 2. Whether there is one or more isolated vertices, F is not a 3-good-neighbor cut of MBn by Claim 1. So, we only need to consider the case that MBni−Fi is connected for i∈2,n. Then MBn2,n−F2,n is connected by Proposition 5. This is same as above. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Note thatF≤8n−25 and 2n−6≤F1≤4n−17. There are at most two Fi′s that can satisfy 2n−6≤Fi≤4n−17, and the others of Fi′s satisfy Fi≤2n−7 for i∈2,n.Firstly, we suppose that there is only oneFi that satisfies 2n−6≤Fi≤4n−17 for i∈2,n. Without loss of generality, we suppose that i=2. Then Fj≤2n−7 for i∈3,n. By Case 2, we only need to consider the case that MBnj−Fj is connected for j∈3,n. MBn3,n−F3,n is connected by Proposition 5. Suppose that none of MBni−Fi is disconnected. Since 2n−2!>8n−34≥F1+F2>F1+F3, we have that MBnVMBni−Fi∪VMBn3,n−F3,n is connected by Proposition 5 for i=1,2. Therefore, MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. Then at least one of MBni−Fi is disconnected for i=1,2. When only one of MBni−Fi is disconnected for i=1,2, this is same as above. When MBn1−F1 is disconnected and MBn2−F2 is disconnected, each of them has seven conditions by Lemma 5. Since 2n−2!>8n−26=24n−17+8≥F1+F2+8 and 2n−2!>6n−20=4n−17+2n−7+4≥F1+Fn+4 when n≥6, we have that MBnVC1∪VC2∪VMBn3,n−F3,n is connected by Proposition 5. Note that VDi≤4 for i∈1,2. If both D1 and D2 are connected to MBn3,n−F3,n, then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. If one of D1 and D2 is a component of MBn−F, neither of the two satisfies the definition of 3-good-neighbor by Claim 2. So, F is not a 3-good-neighbor cut of MBn, a contradiction. If D1 is connected to D2. MBnVD1∪VD2 is a component of MBn−F, and let it be L. Then VL≤8. Whether D1 and D2 is the any condition of Lemma 5, there is at least one vertex u∈VL, and u only has one outside neighbor in L by Proposition 7, so, du≤2. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Secondly, we suppose that there are twoFi′s that satisfy 2n−6≤Fi≤4n−17 for i∈2,n. Without loss of generality, we suppose that i=2,3. Then Fj≤2n−7 for i∈3,n. By the proof above, we consider the case that MBn4,n−F4,n is connected, and none of MBni−Fi is connected for i∈1,3. Note that VDi≤4 for i∈1,3. Since 2n−2!>8n−26=24n−17+8≥Fr+Fs+8 and 2n−2!>6n−20=4n−17+2n−7+4≥Fr+Fn+4 when r,s∈1,3, we have that MBnVC1∪VC2∪VC3∪VMBn4,n−F4,n is connected by Proposition 5. By the proof above, we consider the case that all of Di’s comprise a connected component of MBn−F. Let it be A. By Claim 1, we only consider the case that Di is a K2, a 2-path, or a star with four vertices in Lemma 5 for i∈1,3. Since F is a 3-good-neighbor cut of MBn, the outside neighbors of D1 must be in D2 and D3. Suppose that D1 is a K2 and VK2=v1,v2=3x2x3…xn−221,3x3x2…xn−221 for x2,x3,…,xn−2∈4,n and they differ from each other. Then VK2=v1−,v2−=3x2x3…xn−212,3x3x2…xn−212⊆VD2 and VK2=v1+,v2+=1x2x3…xn−223,1x3x2…xn−223⊆VD3. Suppose that v1−+=2x2x3…xn−213∈VD3 and v2−+=2x3x2…xn−213∈VD3. Note that K2=v1−+v2−+ and K2=v1+v2+ are in D3, and they are not adjacent. So, VD3=4, a contradiction to that D3 is a K2, a 2-path, or a star with four vertices. So, v1−+∈F3 and v2−+∈F3. Since F is a 3-good-neighbor cut of MBn, v1− and v2− must have another neighbor in D2 except themselves, then D2 is not a K2, a 2-path, or a star with four vertices. So, Di is not a K2 for i∈1,3. Suppose that D1 is a 2-path with vertices v1,v2,v3 in this order. Then F1≥3n−1−8=3n−11 by Lemma 5 and F2≤F−F1min−F3min≤8n−25−3n−11−2n−6=3n−8. Note that F2≥4n−1−13=4n−17 when D2 is a star with four vertices. Combining F1≥3n−11=4n−17 when n=6 and F1≥F2, we have that D2 can be a star when n=6. However, MB6i≅B5, and there is no star in B5 by Lemma 5. Therefore, D2 is a 2-path and F2≥3n−1−8=3n−11 by Lemma 5. Then F3≤F−F1min−F2min≤8n−25−23n−11=2n−3. Without loss of generality, we suppose that the 2-path in D1 is v1v2v3. v1,v2,v3=3x2x3x4…xn−221,3x3x2x4…xn−221,3x3x4x2…xn−221 for x2,x3,…,xn−2∈4,n and they differ from each other. By the definition of 3-good-neighbor, v1−=3x2x3x4…xn−212∈VD2, v1+=1x2x3x4…xn−223∈VD3, v3−=3x3x4x2…xn−212∈VD2, and v3+=1x3x4x2…xn−223∈VD3. Combining this with D2 is a 2-path, we have that v2−=3x3x2x4…xn−212∈VD2. Then v1−v2−v3− is a 2-path in D2. At this moment, v1+=1x2x3x4…xn−223∈VD3, v3+=1x3x4x2…xn−223∈VD3, v1−+=2x2x3x4…xn−213∈VD3, and v3−+=2x3x4x2…xn−213∈VD3. Obviously, the four vertices are not adjacent, a contradiction to that D3 is a 2-path or a star with four vertices. Therefore, Di is not a 2-path for i∈1,3. Suppose that D1 is a star with four vertices. Then F1≥4n−1−13=4n−17 by Lemma 5. However, F−F1≤8n−25−4n−17=4n−8, and only one of F2 and F3 can satisfy Fj≥4n−17 for j∈2,3. So, Di is not a star with four vertices for i∈1,3. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Case 4.8≤F1≤11 for n=6.Note that whenn=6, MB6i≅B5 for i∈1,6. κB5=5−1=4 by Proposition 19 and κ2B5=45−3=8 by Proposition 17. F≤8×6−25=23 under this case.Suppose thatFi<4 for i∈2,6. By Case 1, MB62,6−F2,6 is connected. Suppose that MB61−F1 is connected. Since 26−2!=48>15=11+4>F1+F2, we have that MB6−F is connected by Proposition 5, a contradiction to that F is a 3-good-neighbor cut of MB6. Therefore, MB61−F1 is disconnected. Since F1≥8 and F≤23, we have F2,6≤15. Consider the case that MB61−F1 may have one or more small components except C1. Let D1k be the component of MB61−F1 except C1 for k∈Z+. Each vertex in D1k has two outside neighbors in F2,6 by Proposition 6. Combining this with F2,6≤15, we have ∪kVD1k≤7. The component of MB61−F1 does not satisfy the definition of 3-good-neighbor by Claim 2. So, F is not a 3-good-neighbor cut of MB6, a contradiction.SinceF≤23, 8≤F1≤11. There are at most three Fi′s that can satisfy n−2=4≤Fi≤5=2n−7 for i∈2,6. If MB6i−Fi is disconnected, then it has one isolated vertex by Lemma 2 for i∈2,6. Whether there is one or more isolated vertices, F is not a 3-good-neighbor cut of MB6 by Claim 1. Therefore, we only need to consider the case that MB6i−Fi is connected for i∈2,6. Similar to the above, we have that F is not a 3-good-neighbor cut of MB6, a contradiction.Note thatF≤23 and 8≤F1≤11, and there are at most two Fi′s that can satisfy 2n−6=6≤Fi≤7=4n−17 for i∈2,6.Firstly, we suppose that there is only oneFi that satisfies 6≤Fi≤7 for i∈2,6. Without loss of generality, we suppose that i=2. Then Fj≤5 for j∈3,6. Note that when MB6j−Fj is disconnected, it has one isolated vertex by Lemma 2. By Claim 1, we only need to consider the case that MB63,6−F3,6 is connected. Suppose that both MB61−F1 and MB62−F2 are connected. We have that MB6VMB6i−Fi∪VMB63,6−F3,6 is connected by Proposition 5 for i=1,2. So, MB6−F is connected, a contradiction to that F is a 3-good-neighbor cut of MB6. Then at least one of MB6i−Fi is disconnected for i=1,2. When only MB61−F1 is disconnected, this is same as above; when only MB62−F2 is disconnected, MB62−F2 has four conditions by Lemma 3. Note that F1≤11, F2≤7, and VD2≤3. Since 26−2!=48>21=11+7+3≥F1+F2+VD2, we have that MB6VMB61−F1∪VC2∪VMB63,6−F3,6 is connected by Proposition 5. No matter which case D2 is in Lemma 3, there is at least one vertex u∈VD2 with du≤1. Note that MB63,6−F3,6 is connected. u can only has one outside neighbor in ∪kVD1k. Then there is at least one vertex u with du≤2, a contradiction to that F is a 3-good-neighbor cut of MB6. So, we consider the case that MB61−F1 is disconnected and MB62−F2 is disconnected. Note that F1≤11, ∪kVD1k≤7, F2≤7 and VD2≤3. Since 26−2!=48>28=7+11+7+3≥∪kVD1k+F1+F2+VD2 and 26−2!=48>30=23+7≥F1+Fn+∪kVD1k, we have that MB6VC1∪VC2∪VMB63,6−F3,6 is connected by Proposition 5. The same as above, no matter which case D2 is in Lemma 3, there is at least one vertex u∈VD2 with du≤2, a contradiction to F is a 3-good-neighbor cut of MB6.Secondly, we suppose that there are twoFi′s that satisfy 6≤Fi≤7 for i∈2,6. Without loss of generality, we suppose that i=2,3. Then F4,6≤F−F1min−F2min−F3min≤23−8−6−6=3. By the proof above, MBn4,n−F4,n is connected. Note that VD2≤3 and VD3≤3. We only need to consider the case that none of MB6i−Fi is connected for i∈1,3. Since 26−2!=48>28=11+7+7+3≥F1+Fi+∪kVD1k+VD2 and 26−2!=48>13=7+3+3≥F2+F6+VD2 for i∈2,3, we have that MB6VC1∪VC2∪VC3∪VMB64,6−F4,6 is connected by Proposition 5. If one or two of D1k, D2, and D3 comprise a connected component of MB6−F, this is same as above. So, we consider the case that all of D1k, D2, and D3 comprise a connected component of MB6−F, and let it be H. By Lemma 3, each of D2 and D3 has four conditions. By Claim 1, we only consider the case that Di is a K2 or a 2-path for i∈2,3. When D2 is a 2-path with vertices v1,v2,v3 in this order, combining this with MB6≅B5, we have F2≥3+2+2=8. However, when the 2-path is from a 4-cycle, v1 and v3 have another common neighbor, F2≥8−1=7. Then F2=7 and D2 is a 2-path from a 4-cycle under this condition. Since F is a 3-good-neighbor cut of MB6, we have that the outside neighbors of the 2-path are in ∪kVD1k and D3. Without loss of generality, we suppose that v1=1x2x3x432∈VD2 for x2,x3,x4∈4,6 and they differ from each other. Note that v1v2v3 is from a 4-cycle, it has three forms by Proposition 13. The first form is v1=1x2x3x432,v2=v112=x21x3x432,v3=v234=x21x4x332, the second form is v1=1x2x3x432,v2=v123=1x3x2x432,v3=v245=1x3x23x42, and the third form is v1=1x2x3x432,v2=v112=x21x3x432,v3=v245=x21x33x42. Obviously, not all of the outside neighbors of v1 and v3 are in ∪kVD1k and D3. So, the 2-path v1v2v3 does not satisfy the definition of 3-good-neighbor. Therefore, Di is not a 2-path for i∈2,3. When D2 is a K2=v1v2, we have that F2≥2n−6=6 by Proposition 16. Since F is a 3-good-neighbor cut of MB6, we have that the outside neighbors of K2 must be in ∪kVD1k or D3. We suppose that VK2=v1,v2=1x2x3x432,1x3x2x432 for x2,x3,x4∈4,6 and they differ from each other. Furthermore, F2=x21x3x432,1x2x4x332,1x2x33x42;x31x2x432,1x3x4x232,1x3x23x42 by the definition of Bn. N′v1=v1−,v1+=1x2x3x423,2x2x3x431 and N′v2=v2−,v2+=1x3x2x423,2x3x2x431. Obviously, v1−v2−=K2 is in D3 and v1+v2+=K2 is in ∪kVD1k. Note that D3 is a K2 at this moment. Then F3=6. By the definition of 3-good-neighbor, v1−+=3x2x3x421 and v2−+=3x3x2x421 are in ∪kVD1k. Now, v1+,v2+,v1−+,andv2−+ are in ∪kVD1k. By Proposition 6, each of the vertices in ∪kVD1k has another outside neighbor. Obviously, v1−+−=3x2x3x412 and v2−+−=3x3x2x412. Note that D2 is a K2=v1v2. v1−+− and v2−+− must be in F2. Otherwise, they are connected to MB6VC1∪VC2∪VC3∪VMB64,6−F4,6. However, they are different from the vertices in F2. Then F2=6+2=8, a contradiction to the suppose 6≤F2≤7. That means Di is not a K2 for i=2,3. Therefore, F is not a 3-good-neighbor cut of MB6.Note thatF≤23 and 8≤F1≤11. There is only one Fi that can satisfy 8≤Fi≤11 for i∈2,6. Without loss of generality, we suppose that i=2. Note that F3,6≤F−F1min−F2min≤23−8−8=7.WhenMB6j−Fj is connected for j∈3,6, MB63,6−F3,6 is connected by Case 1. Suppose that both MB61−F1 and MB62−F2 are connected. We have MB6−F is connected, a contradiction to that F is a 3-good-neighbor cut of MB6. When one of MB6i−Fi is disconnected for i=1,2, similar to the above, we have that F is not a 3-good-neighbor cut of MB6. Then we consider the case that MB61−F1 is disconnected and MB62−F2 is disconnected. Let D1k be similarly defined as above and let D2l be the component of MB62−F2 except C2 for l∈Z+. Since F3,6≤7, we have ∪kVD1k≤7 and ∪lVD2l≤7 by Proposition 6. Since 26−2!=48>36=11+11+7+7≥F1+F2+∪kVD1k+∪lVD2l and 26−2!=48>25=11+7+7≥F2+F3+∪lVD2l, we have that MB6VC1∪VC2 is connected and MB6VC2∪VMB63,6−F3,6 is connected. Then MB6VC1∪VC2∪VMB63,6−F3,6 is connected. Since ∪kVD1k≤7 and ∪lVD2l≤7, we have that if there is no edge between D1k and D2l, the component in each of them cannot satisfy the definition of 3-good-neighbor by Claim 2. So, we need to discuss the case that at least one of D1k and at least one of D2l comprise a whole component. Let it be S. Any vertex in S has at least one outside neighbor in F3,6 by Proposition 7. Meanwhile, we will prove any vertex in F3,6 is only adjacent with at most one vertex in S. Note that D1k does not satisfy the definition of 3-good-neighbor. Then there is at least one vertex v in ∪kVD1k with d∪kVD1kv≤2. By the proof above, if v+∈F3,6, then v−∈∪kVD1k. Otherwise, if v−∈VC2, then ∪kVD1k is not a component of MB6−F; if v−∈F2, then v has at most two neighbors in S, which means F is not a 3-good-neighbor cut of MB6. Without loss of generality, we suppose that v=x1x2x3x421∈∪kVD1k for x1,x2,x3,x4∈3,6 and they differ from each other. Then v+=1x2x3x42x1∈F3,6 and v−=x1x2x3x412∈∪lVD2l. We suppose that v+=1x2x3x42x1∈F3,6 connects two vertices v and v+−=1x2x3x4x12∈∪lVD2l in S. Now, v−∈∪lVD2l and v+−∈∪lVD2l. Note that NMB62−F2v−=x2x1x3x412,x1x3x2x412,x1x2x4x312,x1x2x31x42 and NMB62−F2v+−=x21x3x4x12,1x3x2x4x12,1x2x4x3x12,1x2x3x1x42. Obviously, v− and v+− have no common neighbor and their neighbors have no common neighbor, too. If v+−+∈VC1, then ∪lVD2l is connected to MB6VC1∪VC2∪VMB63,6−F3,6, a contradiction to that S is a component of MB6−F. If v+−+∈F1, then v+− has at least three neighbors in ∪lVD2l by the definition of 3-good-neighbor. Meanwhile, v− has at least two neighbors in ∪lVD2l. Since v− and v+− have no common neighbor, we have ∪lVD2l=7 and they are two separated components. Note that each vertex in NMB62−F2v+− has at least one outside neighbor in F3,6. Then each vertex in N∪lVD2lv+− has at most one outside neighbor in ∪kVD1k. Therefore, each neighbor of v+− in ∪lVD2l should have another neighbor in ∪lVD2l by the definition of 3-good-neighbor. Combining this with v− and v+− having no common neighbor, we have ∪lVD2l>7, a contradiction to ∪lVD2l≤7. If v+−+∈∪kVD1k, then v+− has at least two neighbors in ∪lVD2l by the definition of 3-good-neighbor. Meanwhile, v− has at least two neighbors in ∪lVD2l. We have ∪lVD2l=6 at this moment. Since each neighbor of v+− in ∪lVD2l should have another neighbor in ∪lVD2l by the definition of 3-good-neighbor. Similar to the above, we have ∪lVD2l>7, a contradiction to ∪lVD2l≤7. Therefore, any vertex in F3,6 is only adjacent with at most one vertex in S. Combining this with F3,6≤7, we have VS≤7. By Claim 2, F does not satisfy the definition of 3-good-neighbor. Therefore, F is not a 3-good-neighbor cut of MB6.WhenMB6j−Fj is disconnected for j∈3,6. Note that F3,6≤7. There is only one MB6j−Fj with Fj≥4 that is disconnected for j∈3,6. Without loss of generality, we suppose that j=3. Then Ft<4 for t∈4,6. By Case 1, MB64,6−F4,6 is connected. If 4≤F3≤5, then MB63−F3 has one isolated vertex by Lemma 2. By Claim 1, we only need to consider the case that MB63,6−F3,6 is connected. The same as above, we have that F is not a 3-good-neighbor cut of MB6. If 6≤F3≤7, then MB63−F3 has four conditions by Lemma 3. By Claim 1, we have to consider the case that D3 is a K2 or 2-path. Note that F1≤11, F2≤11, 6≤F3≤7, ∪kVD1k≤7, F4,6≤1, ∪lVD2l≤7, and VD3≤3. Since 26−2!=48>36=11+11+7+7≥F1+F2+∪lVD2l+∪kVD1k, 26−2!=48>28=11+7+7+3≥F2+F3+∪lVD2l+VD3, and 26−2!=48>11=7+1+3≥F3+F4,6+VD3, we have that MB6VC1∪VC2∪VC3 is connected and MB6VC2∪VMB64,6−F4,6 is connected. Then MB6VC1∪VC2∪VC3∪VMB64,6−F4,6 is connected. By the proof above, we only need to consider the case that at least one of D1k and at least one of D2l and D3 comprise a connected component of MB6−F, and let it be T. If D3 is a 2-path with vertices v1, v2, v3 in this order, similar to the above, we have that D3 is not a 2-path. If D3 is a K2=v1v2, we suppose that VK2=v1,v2=1x2x3x423,1x3x2x423 for x2,x3,x4∈4,6 and they differ from each other. Similar to the above, we can get F3=8, a contradiction to that F3≤7. Then D3 is not a K2. Therefore, F is not a 3-good-neighbor cut of MB6.Case 5.12≤F1≤23 for n=6.Note thatMB6i≅B5 for i∈1,5. F≤23 by Case 4. Then F2,6≤F−F1min≤23−12=11.Suppose thatFi<4 for i∈2,6. By Case 1, MB62,6−F2,6 is connected. By the second paragraph of Case 4, we have to consider the case that MB61−F1 is disconnected. Let D1k be similarly defined as Case 4. Note that F2,6≤11. Since each vertex in D1k has two outside neighbors in F2,6 by Proposition 6, we have ∪kVD1k≤5. The component of MB61−F1 does not satisfy the definition of 3-good-neighbor by Claim 2. So, F is not a 3-good-neighbor cut of MB6, a contradiction.Note thatF2,6≤11. There are at most two Fi′s that can satisfy n−2=4≤Fi≤5=2n−7 for i∈2,6. If MB6i−Fi is disconnected, then it has one isolated vertex by Lemma 2 for i∈2,6. Similar to the third paragraph of Case 4, we have that F is not a 3-good-neighbor cut of MB6, a contradiction.Note thatF2,6≤11. There is only one Fi that can satisfy 2n−6=6≤Fi≤7=4n−17 for i∈2,6. Without loss of generality, we suppose that i=2. Then Fj≤5 for j∈3,6. By the fifth paragraph of Case 4, we have to consider the case that MB61−F1 is disconnected and MB62−F2 is disconnected. Since 6≤F2≤7, we have 12≤F1≤17. Note that MB62−F2 has four conditions by Lemma 3. Then VD2≤3. Since 26−2!=48>32=5+17+7+3≥∪kVD1k+F1+F2+VD2 and 26−2!=48>28=23+5≥F1+Fn+∪kVD1k, we have that MB6VC1∪VC2∪VMB63,6−F3,6 is connected by Proposition 5. No matter which case D2 is in Lemma 3, there is at least one vertex u∈VD2 with du≤1. Note that MB63,6−F3,6 is connected. u can only has one outside neighbor in ∪kVD1k. Then there is at least one vertex u with du≤2, a contradiction to that F is a 3-good-neighbor cut of MB6.Note thatF2,6≤11. There is only one Fi that can satisfy 8≤Fi≤11 for i∈2,6. Without loss of generality, we suppose that i=2. Note that F3,6≤F−F1min−F2min≤23−12−8=3. Then MB63,6−F3,6 is connected by Case 1. By the proof above, we only have to consider the case that MB61−F1 is disconnected and MB62−F2 is disconnected. Let D2l be similarly defined as Case 4. Since F3,6≤3, we have ∪kVD1k≤3 and ∪lVD2l≤3 by Proposition 7. Since 26−2!=48>29=3+23+3≥∪kVD1k+F1+F2+∪lVD2l and 26−2!=48>26=23+3≥F1+Fn+∪kVD1k, we have that MB6VC1∪VC2∪VMB63,6−F3,6 is connected by Proposition 5. By the proof above, we need to consider the case that at least one of D1k and at least one of D2l comprise a connected component of MB6−F, and let it be A. Then VA≤6. Therefore, F is not a 3-good-neighbor cut of MB6 by Claim 2.Case 6.4n−16≤F1≤8n−41 for n≥7.Suppose thatFi<n−2 for i∈2,n. By Case 1, MBn2,n−F2,n is connected. Suppose that MBn1−F1 is connected. Since 2n−2!>8n−25≥F1+F2, we have that MBn−F is connected by Proposition 5, a contradiction to that F is a 3-good-neighbor cut of MBn. Therefore, MBn1−F1 is disconnected. Since κ3Bn−1=8n−40>8n−41 for n≥6, the component of MBn1−F1 does not satisfy the definition of 3-good-neighbor by Proposition 18. So, F is not a 3-good-neighbor cut of MBn, a contradiction.SinceF≤8n−25, 4n−16≤F1≤8n−41. There are at most three Fi′s that can satisfy n−2≤Fi≤2n−7 for i∈2,n. If MBni−Fi is disconnected, then it has one isolated vertex by Lemma 2. Whether there is one or more isolated vertices, F is not 3-good-neighbor cut of MBn by Claim 1. Therefore, we only need to consider the case that MBni−Fi is connected for i∈2,n. Similar to the above, we have that F is not a 3-good-neighbor cut of MBn, a contradiction.Note thatF≤8n−25 and 4n−16≤F1≤8n−41, there are at most two Fi’s that can satisfy 2n−6≤Fi≤4n−17 for i∈2,n.Firstly, we suppose that there is only oneFi that satisfies 2n−6≤Fi≤4n−17 for i∈2,n. Without loss of generality, we suppose that i=2. Then Fj≤2n−7 for j∈3,n. Note that when MBnj−Fj is disconnected, it has one isolated vertex by Lemma 2. By Claim 1, we only need to consider the case that MBn3,n−F3,n is connected. Suppose that both MBn1−F1 and MBn2−F2 are connected. We have that MBnVMBni−Fi∪VMBn3,n−F3,n is connected by Proposition 5 for i=1,2. So, MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. Then at least one of MBni−Fi is disconnected for i=1,2. When only MBn1−F1 is disconnected, this is same as above; when only MBn2−F2 is disconnected, MBn2−F2 has seven conditions by Lemma 5, and this is same as Case 3. So, we consider the case that MBn1−F1 is disconnected and MBn2−F2 is disconnected. Let D1k be the component of MBn1−F1 except C1 for k∈Z+. Note that VD2≤4. Since F2,n≤F−F1min=8n−25−4n−16=4n−9, we have that ∪kVD1k≤2n−5 by Proposition 6. Since 2n−2!>10n−26=8n−25+2n−5+4≥F1+F2+∪kVD1k+VD2 and 2n−2!>6n−20=4n−17+2n−7+4>F2+Fn+4, we have that MBnVC1∪VC2∪VMBn3,n−F3,n is connected by Proposition 5. If both D1k and D2 are connected to MBn3,n−F3,n, then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. If one of D1k and D2 is a component of MBn−F, then by the proof above, neither D1k nor D2 satisfies the definition of 3-good-neighbor. So, F is not a 3-good-neighbor cut of MBn. If all or some of D1k and D2 comprise a connected component of MBn−F, let it be Z. By Lemma 5, whether D1k and D2 are the any condition, there is at least one vertex u∈VZ with du≤2 by Proposition 7. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Secondly, we suppose that there are twoFi′s that satisfy 2n−6≤Fi≤4n−17 for i∈2,n. Without loss of generality, we suppose that i=2,3. Then F4,n≤F−F1min−F2min−F3min≤8n−25−4n−16−22n−6≤3. Note that F1≤F−F2min−F3min≤8n−25−22n−6=4n−13, F2≤F−F1min−F3min≤8n−25−4n−16−2n−6=2n−3, and F3≤F−F1min−F2min≤8n−25−4n−16−2n−6=2n−3. By the proof above, MBn4,n−F4,n is connected. Let D1k be similarly defined as above. Note that VD2≤4 and VD3≤4. We only need to consider the case that none of MBni−Fi is connected for i∈1,3. Since 2n−2!>10n−26=8n−25+2n−5+4≥F1+Fi+∪kVD1k+VD2 and 2n−2!>4n−10=4n−17+3+4>Fi+Fn+4 for i∈2,3, we have that MBnVC1∪VC2∪VC3∪VMBn4,n−F4,n is connected by Proposition 5. If one or two of D1k, D2, and D3 comprise a connected component of MBn−F, this is same as above. So, we consider the case that at least one of D1k, D2, and D3 comprises a connected component of MBn−F, and let it be R. By Lemma 5, each of D2 and D3 has seven conditions. By Claim 1, we only consider the case that Di is a K2, a 2-path, or a star with four vertices in Lemma 5 for i∈2,3. When D2 is a K2=v1v2, we have that F2≥2n−1−4=2n−6 by Lemma 5. Since F is a 3-good-neighbor cut of MBn, we have that the outside neighbors of K2 must be in ∪kVD1k or D3. We suppose that VK2=v1,v2=1x2x3x4…xn−232,1x3x2x4…xn−232 for x2,x3,…,xn−2∈4,n and they differ from each other. N′v1=v1−,v1+=1x2x3x4…xn−223,2x2x3x4…xn−231 and N′v2=v2−,v2+=1x3x2x4…xn−223,2x3x2x4…xn−231. Obviously, v1−v2−=K2 is in D3 and v1+v2+=K2 is in ∪kVD1k. Note that D3 is a K2 at this moment. Then F3≥2n−6 by Lemma 5. By the definition of 3-good-neighbor, v1−+=3x2x3x4…xn−221 and v2−+=3x3x2x4…xn−221 are in ∪kVD1k. Now, v1+,v2+,v1−+,andv2−+ are in ∪kVD1k. By Proposition 6, each of the vertices in ∪kVD1k has another outside neighbor. If v1+−=2x2x3x4…xn−213∈VD3, it is not connected to the K2 in D3, a contradiction to the conditions of D3. So, v1+−∈F3; similarly, we have that v2+−=2x3x2x4…xn−213∈F3, v1−+−=3x2x3x4…xn−212∈F2, and v2−+−=3x3x2x4…xn−212∈F2. Note that F2≥2n−6+2=2n−4 and F3≥2n−6+2=2n−4 at this moment. So, F1≤F−F2min−F3min=8n−25−22n−4=4n−17, a contradiction to F1≥4n−16. Therefore, Di is not a K2 for i=2,3. When D2 is a 2-path with vertices v1,v2,v3 in this order, F2≥3n−11 by Lemma 5. The 2-path is in a 4-cycle when F2=3n−11. Meanwhile, F3≤F−F1min−F2min≤8n−25−4n−16−3n−11=n+2. Note that F3≥3n−11>n+2 when D3 is a 2-path when n≥7, which is a contradiction. Therefore, Di is not a 2-path for i∈2,3. When D2 is a star with four vertices, F2≥4n−1−13=4n−17 by Lemma 5. Note that D3 is a star with four vertices. Then F3≥4n−17. However, F3≤F−F1−F2≤8n−25−4n−16−4n−17≤8<4n−17 when n≥7, which is a contradiction. So, Di is not a star with four vertices for i∈2,3. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Note thatF≤8n−25 and 4n−16≤F1≤8n−41. There is only one Fi that can satisfy 4n−16≤Fi≤4n−13 for i∈2,n. Without loss of generality, we suppose that i=2. Note that F3,n≤F−F1min−F2min≤8n−25−24n−16=7. When F3,n≤7<κBn−1, we have n>9. Then MBn3,n−F3,n is connected by Case 1. Suppose that both MBn1−F1 and MBn2−F2 are connected. Then MBn−F is connected by Proposition 5, a contradiction to that F is a 3-good-neighbor cut of MBn. So, at least one of MBn1−F1 and MBn2−F2 is disconnected. Suppose that MBn1−F1 is connected and MBn2−F2 is disconnected. We have that MBnVMBn1−F1∪VMBn3,n−F3,n is connected by Proposition 5. Let D2l be the component of MBn2−F2 except C2 for l∈Z+. Since F1+F3,n≤4n−9=8n−25−4n−16≤F−F2min, we have that ∪lVD2l≤2n−5 by Proposition 6. Since 2n−2!>10n−30=8n−25+2n−5≥F1+F2+∪lVD2l, we have that MBnVMBn1−F1∪VC2∪VMBn3,n−F3,n is connected by Proposition 7. Combining F3,n≤7 with Proposition 7, we have ∪lVD2l≤7. If all of D2l are connected to MBnVMBn1−F1∪VC2∪VMBn3,n−F3,n, then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. If one or some of D2l are the components of MBn−F, then D2l does not satisfy the definition of 3-good-neighbor by Claim 2. So, F is not a 3-good-neighbor cut of MBn, a contradiction. Suppose that MBn1−F1 is disconnected and MBn2−F2 is connected. This is same as above. Suppose that MBn1−F1 is disconnected and MBn2−F2 is disconnected. Then ∪kVD1k≤7 and ∪lVD2l≤7. Since 2n−2!>8n−19=8n−25+3+3≥F1+F2+∪kVD1k+∪lVD2l and 2n−2!>4n−6=4n−13+7>F2+Fn, we have that MBnVC1∪VC2∪VMBn3,n−F3,n is connected by Proposition 5. If both D1k and D2l are connected to MBn3,n−F3,n, then MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. If one of D1k and D2l is a component of MBn−F, then neither D1k nor D2l satisfies the definition of 3-good-neighbor by Claim 2. If all or some of D1k and D2l comprise a connected component of MBn−F, let it be J. Any vertex in J has at least one outside neighbor in F3,n by Proposition 7. Meanwhile, we will prove any vertex in F3,n is only adjacent with at most one vertex in J. Similar to the proof in Case 4. Without loss of generality, we suppose v=x1x2x3…xn−221 in ∪kVD1k with d∪kVD1kv≤2 for x1,x2,…,xn−2∈3,n and they differ from each other. Then v+=1x2x3…xn−22x1∈F3,n and v−=x1x2x3…xn−212∈∪lVD2l. Suppose that v+ connects another vertex v+−=1x2x3…xn−2x12∈∪lVD2l. Similar to Case 4, we have ∪lVD2l>7, a contradiction to ∪lVD2l≤7. Therefore, any vertex in F3,n is only adjacent with at most one vertex in J. Combining this with F3,n≤7, we have VJ≤7. J does not satisfy the definition of 3-good-neighbor by Claim 2. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction. When n−2≤F3,n≤2n−7, we have 7≤n≤9. Then only one Fj can satisfy n−2≤Fj≤2n−7 for j∈3,n. If MBnj−Fj is connected, then this is same as above. So, MBnj−Fj is disconnected. It has one isolated vertex and a connected component by Lemma 2 for j∈3,n. F is not a 3-good-neighbor cut of MBn by Claim 1. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Case 7.8n−40≤F1≤8n−25 for n≥7.In this case,F2,n≤15. Suppose that Fi<n−2 for i∈2,n. MBni−Fi is connected by Proposition 19. By Case 1, MBn2,n−F2,n is connected. Suppose that MBn1−F1 is connected. By Proposition 5, MBn−F is connected, a contradiction to that F is a 3-good-neighbor cut of MBn. So MBn1−F1 is disconnected. Let D1k be similarly defined as Case 6. Since F2,n≤15, we have that ∪kVD1k≤7 by Proposition 6. Since 2n−2!>8n−18=8n−25+7≥F1+F2+V∪kD1k, we have that MBnVC1∪VMBn2,n−F2,n is connected by Proposition 5. By Claim 2, ∪kVD1k≤7 does not satisfy the definition of 3-good-neighbor. Therefore, F is not a 3-good-neighbor cut of MBn, a contradiction.Note thatMBni≅Bn−1 and κBn−1=n−2. When n>17, we have κBn−1=n−2>15. Combining this with F2,n≤15, we have that MBni−Fi is connected for i∈2,n and n>17. Then MBn2,n−F2,n is connected by Case 1. The same as above, we have that F is not a 3-good-neighbor cut of MBn. When 10≤n≤17, we have 8≤κBn−1=n−2≤15. Then there is only one Fi that can satisfy n−2≤Fi≤2n−7 for i∈2,n. Without loss of generality, we suppose i=2. If MBn2−F2 is connected and MBn2,n−F2,n is connected by Proposition 5, then this is same as above. If MBn2−F2 is disconnected and it has one isolated vertex by Lemma 2, then F is not a 3-good-neighbor cut of MBn by Claim 1. When n=8,9, we have 6≤κBn−1=n−2≤7. Then there are at most two Fi’s that can satisfy n−2≤Fi≤2n−7 for i∈2,n. Without loss of generality, we suppose i=2,3. By the proof above, we have to consider the case that MBnj−Fj is disconnected for j=2,3. MBnj−Fj has one isolated vertex by Lemma 2, and then F is not a 3-good-neighbor cut of MBn by Claim 1. When n=7, we have kBn−1=7−2=5. Then there are at most three Fi’s that can satisfy n−2≤Fi≤2n−7 for i∈2,n. Similar to the above, we have F is not a 3-good-neighbor cut of MBn by Claim 1.Note thatF2,n≤15. When n≥11, we have 2n−6>15. Then there is no Fi that can satisfy 2n−6≤Fi≤4n−17 for i∈2,n and n≥11, this is same as above, and we have F is not a 3-good-neighbor cut of MBn. When 7≤n≤10, we have 8≤2n−6≤14. Then there is only one Fi that can satisfy 2n−6≤Fi≤4n−17 for i∈2,n. Without loss of generality, we suppose i=2. Then Fj≤2n−7 for j∈3,n. By the proof above, we only need to consider the case that MBn4,n−F4,n is connected. Suppose that MBn1−F1 is connected. By Proposition 5, MBnVMBn1−F1∪VMBn4,n−F4,n is connected. Note that 2n−6≤F2≤4n−17. The same as Case 3, we have that F is not a 3-good-neighbor cut of MBn. So, MBn1−F1 is disconnected. Since 2n−2!>8n−18=8n−25+7≥F1+Fn+∪kVD1k, we have that MBnVC1∪VMBn4,n−F4,n is connected by Proposition 5. When MBn2−F2 is connected, MBnVC1∪VMBn2,n−F2,n is connected by Proposition 5. The same as above, we have that F is not a 3-good-neighbor cut of MBn. Then MBn2−F2 is disconnected. And MBn2−F2 has 7 conditions by Lemma 5. Note that ∪kVD1k≤7 and VD2≤4. Since 2n−2!>8n−14=8n−25+7+4≥F1+F2+∪kVD1k+VD2 and 2n−2!>8n−21=8n−25+4≥F2+Fn+VD2, we have that MBnVC1∪VC2∪VMBn3,n−F3,n is connected by Proposition 5. By the proof above, we have to consider the case that at least one of D1k and D2 comprises a connected component of MBn−F. Whether D2 is the any condition of Lemma 5, there is at least one vertex u∈VD2 with dD2u≤1. Since MBn3,n−F3,n is connected, u has only one outside neighbor in ∪kVD1k by Proposition 7. Then du≤2. Therefore, F is not a 3-good-neighbor cut of MBn.There is only oneFi that can satisfy Fi≥4n−16 for i∈2,n. Without loss of generality, we suppose that i=2. Note that F2≥4n−16 and F2,n≤15. We have n=7. Under this condition, F≤8×7−25=31, 16=8×7−40≤F1≤8×7−25=31, 12=4×7−16≤F2≤F−F1≤31−16=15 and F3,7≤15−F2≤3. Then 16≤F1≤19 and MB73,7−F3,7 is connected by Case 1. Suppose that MB71−F1 is connected. Then MB7VMB71−F1∪VMB73,7−F3,7 is connected by Proposition 5. When MB72−F2 is connected, MB7−F is connected by Proposition 5, a contradiction to that F is a 3-good-neighbor cut of MB7. Suppose that MB72−F2 is disconnected. Let D2l be similarly defined as above. Note that MB72≅B6 and 12≤F2≤15. By Proposition 18, κ3B6=8×6−32=16. Then F is not a 3-good-neighbor cut of MB7. Therefore, MB71−F1 is disconnected. Let D1k be similarly defined as above. Combining F3,7≤3 with Proposition 7, we have ∪kVD1k≤3 and ∪lVD2l≤3. Since 27−2!>25=19+3+3≥F1+F7+∪kVD1k, we have that MB7VC1∪VMB73,7−F3,7 is connected. When MB72−F2 is connected, this is same as above. Then MB72−F2 is disconnected. Since 27−2!>21=15+3+3≥F2+F7+∪lVD2l, we have that MB7VC1∪VC2∪VMB73,7−F3,7 is connected by Proposition 5. Since ∪kVD1k≤3 and ∪lVD2l≤3, we have that if there is no edge between D1k and D2l, the component in each of them cannot satisfy the property of 3-good-neighbor by Claim 2. So, we need to discuss the case that at least one of D1k and at least one of D2l comprise a whole component. Let it be Q. Then VQ≤6. F is not a 3-good-neighbor cut of MBn by Claim 2.
By Cases 1–7, ifF is a 3-good-neighbor cut of MBn, then F≥8n−3 for n≥6.Lemma 7.
κ3MBn≤8n−3 for n≥6.Proof.
Choose a subgraphQ3 of MBn with 8 vertices, and let the vertices be ui and vi for i∈1,4. Let A=u1=1,u2=u112,u3=u234,u4=u312;v1=u1n−1,n,v2=u2n−1,n,v3=u3n−1,n,v4=u4n−1,n. Then vi=uin−1,n=ui− for i∈1,4 and A=VQ3. Let A1 and A2 be the vertex sets of the 4-cycle induced by ui and vi, respectively. Obviously, Q3 satisfies the definition of 3-good-neighbor. The vertices in a 4-cycle of Q3 have no other common neighbor by Proposition 4. If u1 and v3 have a common neighbor y, then there is an odd cycle u1yv3u3u2u1, a contradiction to Proposition 1. So, NMBnQ3=8n−3=8n−24 by Proposition 21. Let F1∗=NMBnA and F2∗=A∪NMBnA. MBn−F1∗ has two parts which are denoted by MBn−F2∗ and MBnA. We decompose MBn along the last position, denoted by MBni for i∈1,n. Note that A1⊆VMBnn and A2⊆VMBnn−1. Let FA1∗=NMBnnA1 and FA2∗=NMBnn−1A2. Combining the definition of MBn with Proposition 6, we have that NA∩VMBn1=n234…n−1,1,n243…n−1,1;n−1,234…n1,n−1,243…n1=4. Obviously, VK2=n234…n−1,1,n243…n−1,1 and VK2=n−1,234…n1,n−1,243…n1 are not adjacent. So, MBn1−F1∗ is connected and δMBn1−F1∗≥n−1. Meanwhile, NA∩VMBn2=n134…n−1,2,n143…n−1,2;n−1,134…n2,n−1,143…n2=4. Obviously, VK2=n134…n−1,2,n143…n−1,2 and VK2=n−1,134…n2,n−1,143…n2 are not adjacent. So, MBn2−F2∗ is connected and δMBn2−F1∗≥n−1. Let x∈VMBnn∖A1∪FA1∗. Then x has at most two common neighbors with any one of A1 by Proposition 12. Without loss of generality, we suppose that x has two common neighbors y1 and y2 with u1. If x has one common neighbor y4 with u2 or u4, then there is odd cycle in Bn−1, a contradiction to Proposition 2. If x has one common neighbor y3 with u3, then there are two 6-cycles C1=u1u2u3y3xy1u1 and C2=u1u2u3y3xy2u1 with four common edges, a contradiction to Lemma 1. Then x has no common neighbor with u3. Therefore, Nx∩FA1∗≤2. Note that κBn−1=n−2. We have δx≥n−2−2=n−4≥3 for n≥7; similarly, we have δz≥n−2−2=n−4≥3 for z∈VMBnn−1∖A2∪FA2∗ and n≥7. Note that NA∩VMBni=0 for i∈3,n−2. δMBni>3 by Proposition 19.
Letn=6. Note that A=u1=123456,u2=213456,u3=214356,u4=124356;v1=123465,v2=213465,v3=214365,v4=124365, A1⊆VMB66 and A2⊆VMB65. By the definition of MBn, we have FA1∗=123546,132456;231456,213546;241356,214536;124536,142356=8 and |FA2∗|=8. NA∩VMB61=623451,624351;523461,524361=4. Obviously, VK2=623451,624351 and VK2=523461,524361 are not adjacent. So, MB61−F1 is connected and δMB61−F1∗≥3. NA∩VMB62=613452,614352;513462,514362=4. Obviously, VK2=613452,614352 and VK2=513462,514362 are not adjacent. So, MB62−F2 is connected and δMB62−F1∗≥3. Note that F=NA∩VMB61+NA∩VMB62+FA1∗+FA2∗=24. By the definition of MB6, we have that F1∗∩VMB63=0 and F1∗∩VMB64=0. So, δMB63>3 and δMB64>3. Let x∈VMB66∖A1∪FA1∗. Similar to the above, we have that x has at most two common neighbors with A by Proposition 2 and Lemma 1. Then Nx∩VMB66≤2. Therefore, δx≥4−2+2=4; similarly, δz≥4−2+2=4 for any z∈VMB65∖A1∪FA2∗. Note that δMBnA=3. Therefore, F1∗ is a 3-good-neighbor cut of MBn and κ3MBn≤8n−3.Theorem 1.
κ3MBn=8n−24 for n≥6.


## 4. Conclusions

The modified bubble-sort graph is an important interconnection network topology and it has many good properties. In this paper, we proved that the 3-good-neighbor connectivity of the modified bubble-sort graph is8n−24 when n≥6. We will do further research in the future.



---

*Source: 7845987-2020-10-28.xml*