Mathematics – Combinatorics
Scientific paper
2007-10-11
European Journal of Combinatorics, 30(2), pp. 339-350, 2009
Mathematics
Combinatorics
13 pages
Scientific paper
10.1016/j.ejc.2008.07.001
We say that a graph $G=(V,E)$ on $n$ vertices is a $\beta$-expander for some constant $\beta>0$ if every $U\subseteq V$ of cardinality $|U|\leq \frac{n}{2}$ satisfies $|N_G(U)|\geq \beta|U|$ where $N_G(U)$ denotes the neighborhood of $U$. In this work we explore the process of deleting vertices of a $\beta$-expander independently at random with probability $n^{-\alpha}$ for some constant $\alpha>0$, and study the properties of the resulting graph. Our main result states that as $n$ tends to infinity, the deletion process performed on a $\beta$-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing $n-o(n)$ vertices that is in itself an expander graph, and constant size components. We proceed by applying the main result to expander graphs with a positive spectral gap. In the particular case of $(n,d,\lambda)$-graphs, that are such expanders, we compute the values of $\alpha$, under additional constraints on the graph, for which with high probability the resulting graph will stay connected, or will be composed of a giant component and isolated vertices. As a graph sampled from the uniform probability space of $d$-regular graphs with high probability is an expander and meets the additional constraints, this result strengthens a recent result due to Greenhill, Holt and Wormald about vertex percolation on random $d$-regular graphs. We conclude by showing that performing the above described deletion process on graphs that expand sub-linear sets by an unbounded expansion ratio, with high probability results in a connected expander graph.
Ben-Shimon Sonny
Krivelevich Michael
No associations
LandOfFree
Vertex Percolation on Expander Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Vertex Percolation on Expander Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex Percolation on Expander Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-542103