The Optimalization Of The Isoperimetric-Edge-Connectivity Of Graphs

A classical measurement of the fault tolerance of a network is the edge connectivity. But there are some shortages existed when it measures the dependability of a network. For making up these shortages, Hakimiput forward the conditional edge connectivity. The isoperimetric edge connectivity is a kind of conditional edge connectivity of a graph.The first chapter introduces the graph-theoretical terminology and notation, the ar-rangement of this article.The second chapter studies the isoperimetric edge connectivity of bipartite graphs. We prove that(a) If G has a matching that saturates every vertex in X or every vertex in Y with n≥4 and|N(u)∩N(v)|≥2 for any u, v∈X and any u, v∈Y, then G isγ2-optimal.(b)Let G be a connected bipartite graph of order n and the minimum degreeδ≥3. Ifβ3≥n-2 then G isγ3-optimal.(c)If the minimum degreeδ(G)≥4/n+2k, then G isγk-optimal.Basing on the conclusions of the second chapter, the third chapter studies the isoperi-metric edge connectivity of triangle-free graphs. The main results are(a)Let G be a connected triangle-free graph with order n≥4. If d(u)+d(v)≥2[4/n+2]+1 for each pair u,v∈V(G) with dist(u,v)=2, then G isγ2-ptimal.(b)Let k be a positive integer and let G be a connected triangle-free graph of order n≥2k.If |N(u)∩N(v)|≥k for each pair of u,v with dist(u,v)=2, then G isγk-optimal.