Restricted Edge-connectivity Of Balanced Hypercubes

The balanced hypercube is a very important network topology structure. The connectivity of balanced hypercube is an important research topic. Let G be a finite, simple and undirected graph. A graph G is said to be super edge-connected, if every minimum edge-cut of G isolates a vertex, that is, every minimum edge-cut of G is a set of edges adjacent to a certain vertex with minimum vertex-degree in G. F(?)E(G), if G—F disconnected and G—F every component has at least two vertices, then F is called the restricted edge-cut of G. A graph G is said to be super restricted edge-connected, if every minimum restricted edge-cut of G isolates an edge, that is, every minimum restricted edge-cut of G is a set of edges adjacent to a certain edge with minimum edge-degree in G. If the path P travels all the vertices of G once, the path P is called Hamiltonian path of G. If P=(v1,v2,…,vn-1, vn) is Hamiltonian path, then P is also denoted by (v1,vn)-Hamiltonian path. This thesis mainly investigates the restricted edge-connectivity and edge-fault tolerant Hamiltonion of the balanced hypercube.Chapter1is an introduction part. We introduce some basic definitions of graph theory and connectivity, the relative background of our research and main works.Chapter2introduces the definition and properties of the balanced hypercube. In Section1, we give the definition of the balanced hypercube. Furthermore, in Section2, we give the properties and conclusions of the balanced hypercube.Chapter3proves that the balanced hypercube is maximal edge-connected, super edge-connected and maximal restricted edge-connected. The balanced hy-percube is connected vertex transitive and its degree is k>2. We also prove that the balanced hypercube is super restricted edge-connected though its girth is g=4.Chapter4gives some new properties of the balanced hypercube. Assume that the balanced hypercube has n—1fault edges, we prove that there exists a fault-free (u,v)-Hamiltonian path between any adjacent vertexes u and v, and we also prove that there exists a fault-free Hamiltonian cycle.