Analysis of edge deletion processes on faulty random regular graphs

DOI10.1007/10719839_4MaRDI QIDQ4508361zbMATH OpenFDO

Authors Mike Molloy, Andreas Goerdt, Michael Molloy

Publication date 21 June 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10719839_4

zbMATH Keywords

\(k\)-coreexpandersfault tolerancerandom regular graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80)

Review text

The authors study \(d\)-regular random graphs where each edge can be faulty with a fixed probability \(p\). The main result is a threshold theorem on the fault probability for the existence of a linear size \(k\)-core for any \(k\), \(3\leq k < d\). To formulate the result, denote by \(\text{Bin}(m,\lambda)\) the binomial distribution with parameter \(m\) and success probability \(\lambda\). Consider a real-valued function \(L(\lambda)=\lambda/\text{Pr}[\text{Bin}(d-1,\lambda)\geq k-1]\) defined for \(0<\lambda \leq 1\), and let \(r(k,d)\) be the minimum value of \(L(\lambda)\) in this domain. One can show that the minimum does exist. It is shown that if \(p>r(k,d)\) then a random \(d\)-regular graph has a \(k\)-core of linear size with a high probability. Furthermore, if \(p<r(k,d)\) then the graph has only the empty \(k\)-core with a high probability. This result implies some expansion properties of random regular graphs of a fixed degree. The result is proved by using an attractively simple technique that allows to simplify some known proofs in this area and at the same time to obtain stronger results. For the entire collection see [Zbl 0935.00049].

Recommendations

• Random regular graphs with edge faults: Expansion through cores
• Sudden emergence of a giant k-core in a random graph
• Analysis of edge deletion processes on faulty random regular graphs.
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• The giant component threshold for random regular graphs with edge faults

Cited in

(6)

• Analysis of edge deletion processes on faulty random regular graphs.
• A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
• Random Deletion in a Scale-Free Random Graph Process
• Connectivity properties in random regular graphs with edge faults
• The partial duplication random graph with edge deletion
• Random regular graphs with edge faults: Expansion through cores

This page was built for publication: Analysis of edge deletion processes on faulty random regular graphs

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