Skip to main content
3 of 3
During my rewrite, I accidentally misstated the concept the OP is asking for in the new *title*. Corrected.

Subsets of a graph, maximal w.r.t. the property of inducing a subgraph with minimum degree at least $k$

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).

Ozzy
  • 393
  • 2
  • 12