Hypercube Restricted Edge Connectivity And Reliability

The traditional measure for reliability of telecommunication networks is edge conntectiV-ity of graphs,but it cannot estimate accurately the degree a network fails.m-restricted edge connectivity of grahps is a more measure,it make up the previous flaw.An edge Cut of a con-nected graph is m-restricted if its removal leaves every component having order at least m.The size of minimum m-restricted edge cuts of a graph G is called its m-restricted edge connec-tivity.Hypercube,or n-cube,Qn is an important network topology,it has vertex set V(Qn)={χnχn-1...χ1:χi∈{0,1},i=1,2,...,n},where verticesχ=χnχn-1...χ1and y=ynyn...y1are adjacent to each other if and only if∑i=1n|χi-yi|=1.This work studies the m-restricted edge connectivity and reliability of hypercube networks. As a result,explicit expressions of m-restricted edge connectivity of these networks are pre-sented as well as the methodology on optimization of their m-restricted edge connectivity,reli-ability analysis are also presented.Our main results are as follows.Theorem2.3.4For any positive integerκ≤n-1,if m=2κthen n-cube Qn is maximally m-restricted edge connected.Theorem2.3.5For every1≤m≤2n/2-1,n-cube Qn is maximally m-restricted edge connected.Corollary2.3.6If1≤m≤2n/2-1.or m=2k≤2n-1,then λm(Qn)=mm-(kp2kp+···+k12k1+2kp-1+1+2×2kp-2+1+···+(p-1)2k1+1+2pq),where k is a positive integer.Theorem4.1.1. Let Ch be the number of edge cuts of n-cube with size h.If n≥4and4n-8>h≥3n-4,thenTheorem4.2.5If n≥4,then the number of edge cut of Qn with size4n-8≤h≤5n-11 ISwhereand...