Let G=(V,E) be a given network. Denote by $S_k \subset V$ be the maximal subset of nodes such that in the induced subgraph $G_k=(S_k, E_k)$ (where $E_k=E\cap S_k \times S_k$), all agents have at least $k$ connections, i.e., $i\in S_k \Rightarrow \sum_{j\in S_k} g_{ij}\geq k$, where $G$ denotes the unweighted adjacency matrix.

My question is whether for a given $k$ the set $S_k$ corresponds to a known quantity in the graph theory literature. I am interested in understanding how the cardinality of set $S_k$ changes as a function of $k$ for different families of graphs (or certain random graph models).

Let $G=(V,E)$ be a simple undirected graph. Define an mmd$k$s in $G$ (for 'maximal minimum degree $k$ subset') to be any subset $S$ of $V$ such that

1. the subgraph induced by $S$ in $G$ has minimum degree $\geq k$,
2. $S$ is $\subseteq$-maximal w.r.t. property 1.

Moreover, for any $k$, let $\mathrm{smmds}(G,k):=\sup\{ \lvert S \rvert \colon\text{$S$ is an mmd$k$s in $G$}\}$.

Moreover, for any class $\mathbb{G}$ of graphs, let $\mathrm{smmds}(\mathbb{G},k):=\sup\{ \mathrm{smmds}(G,k)\colon G\in\mathbb{G}\}$.

My question is whether

• mmd$k$s's
• the graph invariant $\mathrm{smmds}(\cdot,k)$,

have already been analysed and named in graph theory. 

I am interested in understanding how $\mathrm{smmds}(\cdot,k)$, varies, as a function of $k$, for different families of graphs (or certain random graph models).