Random regular graphs with edge faults: Expansion through cores

DOI10.1016/S0304-3975(00)00215-2MaRDI QIDQ5941563zbMATH OpenFDO

Authors Andreas Goerdt

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00215-2

zbMATH Keywords

communication networkfaulty random regular graphs

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Review text

Let \(G\) be a given graph (modelling a communication network) which we assume suffers from static edge faults: That is we let each edge of \(G\) be present independently with probability \(p\) (or absent with fault probability \(f=1-p)\). In particular, we are interested in robustness results for the case that the graph \(G\) itself is a random member of the class of all regular graphs with given degree \(d.\) Here we deal with expansion properties of faulty random regular graphs and show: For fixed \(d\geqslant 42\) and \(p=\kappa/d,\kappa \geqslant 20\), a random regular graph with fault probability \(f= 1-p\) contains a linear-size subgraph which is an expander almost surely. This subgraph can be found by a simple linear-time algorithm.

Recommendations

• Expander properties in random regular graphs with edge faults
• Connectivity properties in random regular graphs with edge faults
• scientific article; zbMATH DE number 1361486
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• On random digraphs and cores
• Expansion of random graphs: new proofs, new results
• Random Regular Graphs: Asymptotic Distributions and Contiguity

Cites work

• Efficient self-embedding of butterfly networks with random faults
• Expander properties in random regular graphs with edge faults
• scientific article; zbMATH DE number 437557 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 48363 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1256692 (Why is no real title available?)
• scientific article; zbMATH DE number 1512674 (Why is no real title available?)
• scientific article; zbMATH DE number 1361486 (Why is no real title available?)
• scientific article; zbMATH DE number 3349081 (Why is no real title available?)
• On the fault tolerance of the butterfly
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Sudden emergence of a giant k-core in a random graph
• The isoperimetric number of random regular graphs

Cited in

(9)

• Finding a target subnetwork in sparse networks with random faults
• Analysis of edge deletion processes on faulty random regular graphs.
• The mixing time of the giant component of a random graph
• scientific article; zbMATH DE number 1512674 (Why is no real title available?)
• Expander properties in random regular graphs with edge faults
• scientific article; zbMATH DE number 1361486 (Why is no real title available?)
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• The effect of faults on network expansion
• Expansion properties of a random regular graph after random vertex deletions

This page was built for publication: Random regular graphs with edge faults: Expansion through cores

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5941563)