The λ_3,q-connectivity Of Graphs And The Optimally Local-connectivity Of Transitive Graphs

With the rapid development of information networks, many theoretical problems comeinto focus, one of which is the reliability of the network, that is, the ability of the networkto function even when some vertices and/or edges fail. Using graphs to serve as thetopologies of networks has been widely accepted and utilized by computer scientists. Theconcept of traditional vertex(edge) connectivity in graph theory is an important measurefor networks, but the traditional vertex(edge) connectivity has a huge limitation, it alwaysunderestimates the the resilience of large networks. With the inceasing development oflarge networks, it is necessary to improve on the concept of traditional connectivity.Motivated by this, Harary introduced the concept of conditional connectivity. A morerefined measure known as restricted edge connectivity was proposed by Esfahanian andHakimi in 1988, which was generalized to k-restricted edge connectivity by F′abrega andFiol . These concepts were generalized to (p,q)-restricted case as follow. An edge subsetS of G is a (p,q)-restricted edge cut if there are two components of G - S which have atleast p and q vertices, respectively. The cardinality of the minimum (p,q)-restricted edgecut is called the (p,q)-restricted edge connectivity of G, denoted byλp,q(G).On the other hand, the local (edge) connectivity is also an important measure fornetworks. The local connectivityκ(u,v) of two vertices u and v in a graph G is themaximum number of vertex-disjoint u-v paths in G,and the vertex-connectivity of G isexactlyκ(G) = min{κ(u,v) | u,v∈V (G),u = v}. Clearly,κ(u,v)≤min{d(u),d(v)} forall pairs u and v of vertices in G. We call a graph G optimally local-vertex-connectedifκ(u,v) = min{d(u),d(v)} for all pairs u and v of vertices in G. Similarly, we candefine the local edge connectivityλ(u,v) of a graph G and a graph G to be optimallylocal-edge-connected.In this thesis, we have two works. First, we will present some conditions for graphsto beλ3,q-connected using spanning tree. Second, we will prove that all edge transitivegraphs are optimally local-edge-connected.