Restricted Edge Connectivity Of De Bruijn Digraphs And Graphs

Graphs are often as models for the multiprocessor interconnect networks, in which the vertex set corresponds to processors, and the edge set corresponds to communication links. In this case, some properties of the graphs correspond to the capability of the networks. One fundamental consideration in the design of such networks is overall reliability, which can usually be measured by the connectivity or the edge-connectivity of the graphs. Since there are some limitations in measuring the reliability by the the connectivity or the edge-connectivity, the restricted edge connectivity, as a generalization of classical edge connectivity, was introduced by Esfahanian and Hakimi. Let G be an undirected, simple and connected graph. A restricted edge-cut F of G is an edge cut such that G — F has no isolated vertex. The restricted edge-connectivity X'(G) is the minimum cardinality over all restricted edge-cuts. The restricted edge connectivity is an important measure of fault-tolerance for interconnection networks. The super restricted edge connectivity provides a more accurate index of fault-tolerance of networks. G is called a super restricted edge connected graph if every minimum restricted edge cut separates exactly one edge. In this thesis, we mainly study the restricted edge connectivity for the de Bruijn digraphs and the super restricted edge connectivity for the de Bruijn undirected graphs.In Chapter 1, after a short introduction to the used basic notation and terminology on graphs, we give in Section 1.2 some concepts and properties on de Bruijn graphs, and give in Section 1.3 some concepts and basic results connectivity.De Bruijn graphs, as an important topology model of de Bruijn networks, were widely studied. But there are few results on the restricted edge connectivity of de Bruijn digraphs. In Chapter 2, we consider restriced edge connectivity of de Bruijn digraph B(d, n) and obtain the following results: λ'(B(d, n)) = 2d—2 for d > 3, n > 2 or d — 2, n > 3, which implies that those de Bruijn digraphs are super edge connectivity.In Chapter 3, we consider the super restriced edge connectivity of de Bruijn undirected graph UB(d, n) on the basis of some old results, and obtain the following results: if the order of de Bruijn undirected graph UB(d, n) is not less than 4, then it is super restriced edge connected, unless d = 2 and n > 3. Furthermore, we analyze the super restriced edge connectivity for all de Bruijn undirected graphs.