Expansion properties of a random regular graph after random vertex deletions

DOI10.1016/J.EJC.2007.06.021zbMATH Open1153.05063arXivmath/0701863OpenAlexW2058466367MaRDI QIDQ925017FDOQ925017

Catherine Greenhill, Nicholas Wormald, Fred B. Holt

Publication date: 29 May 2008

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Paths in graphs
• Title not available (Why is that?)
• The isoperimetric number of random regular graphs
• Percolation on finite graphs and isoperimetric inequalities.
• The mixing time of the giant component of a random graph
• Sampling Regular Graphs and a Peer-to-Peer Network
• Edge percolation on a random regular graph of low degree
• Analysis of edge deletion processes on faulty random regular graphs.
• CONNECTIVITY PROPERTIES IN RANDOM REGULAR GRAPHS WITH EDGE FAULTS
• Random regular graphs with edge faults: Expansion through cores

Cited In (7)

• The sharp threshold for percolation on expander 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
• Random Deletion in a Scale-Free Random Graph Process
• The partial duplication random graph with edge deletion

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)