Extra Connectivity Of Folded Hypercubes

Connectivity is important for measuring the fault tolerance of a multiprocessor system.Extra connectivity is a vital parameter of a network’s ability for diagnosis and fault-tolerance.We say a set F has property?_gif|F|>g.A subset S?V（G）is an?_g-cut of G if G-S is disconnected and every component of G-S has property?_g.The g-extra connectivity of G,denoted byκ_g（G）,is min^{F_F?V（G）|F||F is an?_g-cut of G}.n-dimensional folded hypercube F Q_n is one of the variants of n-dimensional hy-percubes,its vertex set equal to n-dimensional hypercubes’s vertex set,its edge is point pairs which Hamming distance is 1 or n.In Chaper3 and Chaper4 we discuss the minimum neighborhood problem in a folded hypercube.In Chaper5 we give an upper and a lower bound of theκ_g（F Q_n）for n+1≤g≤2n-5 and n≥22,we show that θ_g（Q_n）+n≤κ_g（F Q_n）≤θ_g（Q_n）+g-1,whereθ_g（Q_n）=-₁/2g²+（2n-₃/2）g-（n²-2）.