distance to maximum degree

• unknown
  • maximum degree $k$ upper bounds distance to maximum degree by $\mathcal O(k)$ – by definition
  • h-index $k$ upper bounds distance to maximum degree by $\mathcal O(k)$ – Remove the $h$ vertices of degree at least $h$ to get a graph that has maximum degree $h$.
  • distance to maximum degree $k$ upper bounds h-index by $\mathcal O(k)$ – Removal of $k$ vertices yielding a graph with maximum degree $c$ means that there were $k$ vertices of arbitrary degree and the remaining vertices had degree at most $k+c$. Hence, $h$-index is no more than $k+c$.