# Efficiently generate a random subgraph (Gs) with maximum degree K, using only edges from an existing graph G

I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the subgraph has only nodes with degree $k \leq k_{max}$.

In other words, I want to create a new random graph with the same number of vertices, but with a random set of the original edges from $G$ removed such that the maximum degree of the new graph is less than some threshold.

I have already developed a working algorithm (MATLAB) which randomly prunes edges from nodes with degree $k > k_{max}$ until this condition is met - however I feel it is far from optimal. It is important that the new random subgraph has the same number of vertices and remains undirected (symmetric). Disconnected vertices (with no in/out edges are allowed).

Ideally both original graph $G$ and new random subgraph $G_s$ should result in sparse matrices (i.e. an edge list), however a full adjacency matrix will suffice.

Thanks!!

• Are you looking for any special kind of randomness properties? – Raziman T V Jan 13 '17 at 17:40
• Somehow my question was added when I wasn't logged in properly! Raiziman T.V. - I'm not necesarily looking for special randomness properties. – Adam Zienkiewicz Jan 13 '17 at 18:29