λ_k-Optimality Of Complete Bipartite Graphs And Harary Graphs

With the rapid development of communication networks, many theoretical problemshave come into focus, one of which is the stability of the networks. The stability of anetwork measures the capability of a network to be still functioning in the presence ofsome failures of the components. This is one of the elementary considerations in designingand constructing a network. A network can be modeled as a graph, and the stability of thenetwork can be measured by various kinds of connectivities of the corresponding graph.We study one kind of them in this dissertation, which is restricted-edge-connectivity.An edge subset S of a connected graph G = (V,E) is a k-restricted-edge-cut if G - Sis disconnected, and every component of G-S has at least k vertices. The k-restricted-edge-connectivity of G, denoted byλ_k(G), is the cardinality of a minimum k-restricted-edge-cut. From recent studies on this parameter, it seems that the largerλ_k is, the morestable the network is. Defineξ_k(G) = min{ω(S) : (G),|S| = k and G[S] isconnected}, whereω(S) = |[S,V (G)\S]| is the number of edges with one end in S andthe other end in V (G)\S. In large number of cases,ξ_k(G) is an upper bound forλ_k(G).Hence it is defined in the literature that a graph G is calledλ_k-optimal ifλ_k(G) =ξ_k(G).The question can be answered affirmatively by studying complete bipartite graphs.Furthermore, we found that Harary graphs with the first type and the second type arealsoλ_k-optimal. In fact, the values ofλ_k(G) are calculated.This dissertation is organized as follows. In Section 1.1, we introduce brie?y thebackground of this parameter, and some terminologies. Section 1.2 presents the mainresults. Chapter 2 is devoted to proving the main results. Theλ_k-optimality of completebipartite graphs, first type Harary graphs (which are also known as powers of cycles), andsecond type Harary graphs are proved respectively in Section 2.1, 2.2, and 2.3. The mainmethod used in the proof is introduction.