Graph Connectivity And Non-separating Subgraphs

With the rapid development of information networks, the fault toleranceand the connectedness of networks draws more and more attention of re-searchers. The thesis studies the connectedness of a graph and its fault toler-ance by studying connectivity and non-separating subgraph.Let G be a graph. A vertex subset S of G is called avertex cut of G if G Sis disconnected. The order of a minimum vertex cut is called the connectivityof G, denoted by_κ(G). A subgraph H of G is called anon-separating subgraphif G—V (H) is still connected. These two concepts give some descriptions ofthe reliability of a network in diferent aspects.In Chapter1, we briefly introduce the significance of (edge) connectivity inoptimized network designment, some related terminologies and some relatedresults. Then state the famous path-removable conjecture due to Lov′asz andsome known result about this conjecture.In Chapter2, we study the vertex fault tolerance with respect to optimal-κ and super-κ, respectively. If a graph G satisfies_κ(G)=δ(G) then G iscalled maximally connected or optimal-_κ. If every minimum vertex cut is theneighborhood of some vertex then G is said to be super-_κ. An optimal-_κ (orsuper-κ) graph G is said to be m-optimal-_κ (or m-super-_κ) if G S is stilloptimal-_κ (or super-_κ) for any vertex set S of order at most m. The maximumvalue of such m is called the vertex fault tolerance with respect to optimal-κ (orsuper-κ), denoted by O__κ(G)(or S_κ(G)). In Chapter2, we find an upper boundand a lower bound to O__κ(G) and S_κ(G), respectively. Then we also show thatfor any value between the upper bound and the lower bound, there is a graphwhose O__κ(G)(or S_κ(G)) equals to this value. Finally, for any positive integersa, b, we give a sufcient and necessary condition to whether there is a graphG such that O__κ(G)=a and S_κ(G)=b.In Chapter3, we consider non-separating subgraphs. There is a famousconjecture due to Lov′asz which says for any positive integer k, there is aminimum integer f(k) such that for any f(k)-connected graph G and any twovertices s and t, there is a path P connecting u and v such that G—V (P)is k-connected. In Chapter3, we consider some generalizations or varieties ofLov′asz conjecture as follows. First, for any positive integers k, l, there is a minimum integer f(k, l) suchthat any f(k, l)-connected graph G and any vertex subset of order k and anyedge not incident with X, there is a cycle C such that e∈E(C), V (C)∩X=and G—V (C) is l-connected. In Chapter3, we use linkage theory to showf(k,1)≤10k+1and f(k,2)≤10k+11.Second, for any positive integers k, l, there exists a minimum integer g(k, l)such that for any g(k, l)-connected graph G and any vertex subset X of orderk, there a cycle C such that V (C)∩X=and G—V (C) is l-connected. InChapter3, we show that g(k, l)≤2k+l+2by finding a contractible edge, andwhen l=1, g(k,1)=k+3. In fact, we also characterize the counterexampleof (k+2)-connected graph which has no such cycles.Finally, for any positive integers k, l, there is a minimum integer h(k, l) suchthat any h(k, l)-connected graph G and any vertex set X of order k, there is atree connecting X such that G—V (T) is l-connected, where a tree connectingX is a tree whose vertex set contains X and leaves lie in X. In Chapter3, wealso shows h(k,1)=k+1, h(k,2)≤2k+1.