Name
Title | ||
|---|---|---|
Conditional edge connectivity properties, reliability comparisons and transitivity of graphs |
Abstract | ||
|---|---|---|
The ith conditional edge-connectivity λi for a (simple) graph G is the minimum cardinality of a set of edges, if any, whose deletion disconnecting G and every remaining component has more than i vertices. The usual edge connectivity λ and the restricted edge connectivity λ′ of G correspond to λ0 and λ1, respectively. We first give an improved reliability comparison criterion between two regular graphs by means of λ0,λ1 and λ2. Next we prove that a vertex-transitive graph with degree d⩾4 and girth g⩾5 or an edge-transitive d-regular graph with degree d⩾4 and girth g⩾4 must have the maximum λi, namely, λi=(i+1)d−2i for 0⩽i⩽min(g−2,n/2−1), where n is the order of the graph. Finally, as an application of the above results, we show that both Ka,a(a⩾4) and Ka+1,a+1−(a+1)K2(a⩾5) are the most reliable graphs for sufficiently small edge failure probabilities. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0012-365X(02)00299-6 | Discrete Mathematics |
Keywords | Field | DocType |
Conditional edge connectivity,Vertex-transitive,Edge-transitive,Locally the most reliable | Discrete mathematics,Strongly regular graph,Combinatorics,Line graph,Graph power,Cycle graph,Independent set,Regular graph,Symmetric graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
258 | 1 | 0012-365X |
Citations | PageRank | References |
50 | 2.25 | 0 |
Authors | ||
2 | ||