Return to Answer

According to Wikipedia, the $k$-core of a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until there are no such vertices left (note that this may terminate with $S_k=\emptyset$).

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

According to Wikipedia, a $k$-core of a graph $G$ is a maximal connected subgraph $K$ of $G$ such that every vertex of $K$ has degree at least $k$. Apart from the "connected" part of the definition, this is the same as your set $S_k$. Your set $S_k$ is the union of the vertex sets of all $k$-cores of $G$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until there are no such vertices left (note that this may terminate with $S_k=\emptyset$).

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

According to Wikipedia, the $k$-core of a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left.

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

According to Wikipedia, the $k$-core of a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until there are no such vertices left (note that this may terminate with $S_k=\emptyset$).

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

According to Wikipedia, a $k$-core in a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left.

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.

According to Wikipedia, the $k$-core of a graph is a maximal connected subgraph in which every vertex has degree at least $k$. This is the same as your set $S_k$.

Similar to what Gerhard suggested, you can find the set $S_k$ by initialising $S_k:=V(G)$ and then repeatedly deleting every vertex of degree less than $k$ in the subgraph induced by $S_k$ until either $S_k=\emptyset$ or there are no such vertices left.

With regards to $k$-cores in random graphs, one natural place to start might be the paper Size and connectivity of the $k$-core of a random graph by Tomasz Łuczak.