Conditional Connectivity Of K-regular Graph With Two Orbits

Using graph to study the topology of the network has been widely accepted andapplied by computer scientists, The concept of (edge)connectivity in graph theory is animportant measure for networks, which can correctly re?ects the fault tolerance of systemswith few processors, but it always underestimates the the resilience of large networks.With the development of multiprocessor systems, it is necessary to improve the conceptof traditional connectivity. Motivated by the shortcomings of the traditional connectivity,Harary [4] introduced the concept of conditional connectivity.Let G be a connected undirected graph, and P be a graph-theoretic property, Harary[4] defined the conditional edge connectivityλ(G;P) as the minimum cardinality of aset of edges, if any, whose deletion disconnects G and every remaining component hasproperty P. Let g be a non-negative integer, and Pg be the property of having at leastg vertices. An edge set F is called a restricted edge-cut if G ? F is disconnected andcontains no isolated vertices. The minimum cardinality over all restricted edge-cuts iscalled restricted edge-connectivity of G, and denoted byλ(G). A graph G is calledλ-optimal ifλ(G) =ξ(G), whereξ(G) = min{dG(u) + dG(v) ? 2 : uv∈E(G)}. A cyclicedge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has acyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graphG, the cyclic edge-connectivity cλ(G) is the cardinality of a minimum cyclic edge-cut ofG. Letζ(G)=min{ω(X)|X induces a shortest cycle in G}, whereω(X) is the number ofedges with one end in X and the other end in V (G) ? X. A cyclically separable graph Gwith cλ(G) =ζ(G) is said to be cyclically optimal. In this paper, we obtain a su?cientcondition for a k(≥3)-regular connected graph with two orbits to beλ-optimal. Wediscuss the cyclic edge connectivity of regular double-orbit graphs.