On conditional edge-connectivity of graphs

Letk andh be two integers, 0≤h<k. LetG be a connected graph with minimum degree at leastk. The conditionalh-edge-connectivity ofG, denoted by λ( ^h )(G), is defined as the minimum cardinality ⋎S⋎ of a setS of edges inG such thatG-S is disconnected and is of minimum degree at leasth. This type of edge-connectivity is a generalization of the traditional edge-connectivity and can more accurately measure the fault-tolerance of networks. In this paper, we will first show that λ²(G)≤g(k-2) for ak(≥3)-regular graphG providedG is neitherK ₄ andK ₅ norK _3,3 , whereg is the length of a shortest cycle ofG, then show that λ( ^h )(Q _k )=(k-h)2 ^h for ak-dimensional cubeQ _k . This work is supported partially by the National Natural Science Foundation of China (No. 19971086).