Existence of Small Separators Depends on Geometry for Geometric Inhomogeneous Random Graphs

2017/11/10 by Johannes Lengler, Lengler, Johannes, Lazar Todorović +1 · 1 citation
Mathematics · Computer Science · Physics and Astronomy · #Stochastic processes and statistical mechanics #Optimization and Search Problems #Complex Network Analysis Techniques

paper · pdf · doi:10.48550/arxiv.1711.03814

Abstract

We show that Geometric Inhomogeneous Random Graphs (GIRGs) with power law weights may either have or not have separators of linear size, depending on the underlying geometry. While it was known that for Euclidean geometry it is possible to split the giant component into two linear size components by removing at most n^1-\eps edges, we show that this is impossible if the geometry is given by the minimum component distance.

Cited by

• Stopping explosion by penalising transmission to hubs in scale-free spatial random graphs

Related

• On the Giant Component of Geometric Inhomogeneous Random Graphs
• Sampling Geometric Inhomogeneous Random Graphs in Linear Time
• Sublinear Cuts are the Exception in BDF-GIRGs
• On the Probability of the Existence of Fixed-Size Components in Random Geometric Graphs
• The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs