Extremal Graphs With Maximum Edge-Neighbor-Connectivity

The focus of this thesis is the spy network. One measure of the reliability of spynetwork is the edge-neighbor-connectivity. An edge is subverted if its two ends are deletedfrom the graph. The edge-neighbor-connectivity of graph G, denoted as λNB(G), is theminimum number of edges the subversion of which results in a graph which is eitherempty, or trivial, or disconnected.This thesis is divided into four chapters. In Chapter1, we introduce the backgroundand the current studies on (edge-)neighbor-connectivity. For a graph G with order n, it isknown that λNB(G)≤n/2. The major contribution of this thesis is a characterizationof all the extremal graphs whose edge-neighbor-connectivity achieve the upper bound.Chapter2contains some preliminary results, in particular, a necessary and sufcientcondition for λNB(G)=n/2is obtained. By this condition, Chapter3shows that foreven n, the only extremal graphs are the complete graph Knand the complete bipartitegraph Kn2,n2. Chapter4proves that for odd n, the extremal graphs can only be the5-cycle C₅, or Kn M0(the complete graph with a matching M0removed), or the graph Gspanned by a Kn2,n2such that the n/2-part is independent in G and the n/2-parthas matching number at most one.