maximum degree
- 2013 Belmonte2013
- carving-width $k$ upper bounds maximum degree by $\mathcal O(k)$ – Observation 1. Let $G$ be a graph. Then $cw(G) \ge \Delta(G)$.
- 2010/08 Sasak2010
- page 28 : cutwidth $k$ upper bounds maximum degree by $\mathcal O(k)$ – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
- unknown
- pathwidth+maxdegree $k$ upper bounds maximum degree by $\mathcal O(k)$ – by definition
- maximum degree upper bounds distance to maximum degree by a constant – by definition
- maximum degree $k$ upper bounds h-index by $\mathcal O(k)$ – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
- bandwidth $k$ upper bounds maximum degree by $\mathcal O(k)$ – Each vertex has an integer $i$ and may be connected only to vertices whose difference from $i$ is at most $k$. There are at most $k$ bigger and $k$ smaller such neighbors.
- maximum degree – maximum degree of graph’s vertices
- grid upper bounds maximum degree by a constant
- bounded planar does not imply bounded maximum degree
- SchroderThesis
- page 24 : bounded vertex cover does not imply bounded maximum degree – Proposition 3.19
- page 28 : bounded maximum degree does not imply bounded clique width – Proposition 3.26
- page 28 : bounded maximum degree does not imply bounded bisection bandwidth – Proposition 3.26