Expansion properties of a random regular graph after random vertex deletions

DOI10.1016/J.EJC.2007.06.021MaRDI QIDQ925017zbMATH OpenOpenAlexFDO

Authors Catherine Greenhill, Fred B. Holt, Nicholas Wormald

Publication date 29 May 2008

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701863

zbMATH Keywords

random regular graphvertex deletionsgraph expanders

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We investigate the following vertex percolation process. Starting with a random regular graph of constant degree, delete each vertex independently with probability p, where p=n^{-alpha} and alpha=alpha(n) is bounded away from 0. We show that a.a.s. the resulting graph has a connected component of size n-o(n) which is an expander, and all other components are trees of bounded size. Sharper results are obtained with extra conditions on alpha. These results have an application to the cost of repairing a certain peer-to-peer network after random failures of nodes.

Recommendations

• Vertex percolation on expander graphs
• Analysis of edge deletion processes on faulty random regular graphs.
• Random regular graphs with edge faults: Expansion through cores
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• Expander properties in random regular graphs with edge faults

Cites work

• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Analysis of edge deletion processes on faulty random regular graphs.
• Connectivity properties in random regular graphs with edge faults
• Edge percolation on a random regular graph of low degree
• Paths in graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Random regular graphs with edge faults: Expansion through cores
• Sampling Regular Graphs and a Peer-to-Peer Network
• The isoperimetric number of random regular graphs
• The mixing time of the giant component of a random graph

Cited in

(11)

• The partial duplication random graph with edge deletion
• Expanders via local edge flips
• The sharp threshold for percolation on expander graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Expansion and Lack Thereof in Randomly Perturbed Graphs
• Characterizing optimal sampling of binary contingency tables via the configuration model
• Vertex percolation on expander graphs
• r 3: Resilient Random Regular Graphs
• The expansion and mixing time of skip graphs with applications
• Expander properties in random regular graphs with edge faults
• Random Deletion in a Scale-Free Random Graph Process

This page was built for publication: Expansion properties of a random regular graph after random vertex deletions

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