minimum degree

• 1998 Bodlaender1998
  • page 38 : treewidth $k$ upper bounds minimum degree by $\mathcal O(k)$ – Lemma 90 (Scheffler [94]). Every graph of treewidth at most $k$ contains a vertex of degree at most $k$.
• unknown
  • minimum degree $k$ upper bounds edge connectivity by $\mathcal O(k)$ – Removing edges incident to the minimum degree vertex disconnects the graph.
  • minimum degree $k$ upper bounds domatic number by $\mathcal O(k)$ – The vertex of minimum degree needs to be dominated in each of the sets. As the sets cannot overlap there can be at most $k+1$ of them.
  • average degree $k$ upper bounds minimum degree by $\mathcal O(k)$ – By definition
  • minimum degree – minimum degree of graph’s vertices