vertex integrity

• unknown
  • vertex integrity $k$ upper bounds treedepth by $\mathcal O(k)$ – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
  • vertex integrity $k$ upper bounds distance to bounded components by $\mathcal O(k)$ – By definition
  • distance to bounded components $k$ upper bounds vertex integrity by $\mathcal O(k)$ – By definition
  • vertex integrity – Minimum $k$ such that there exists $k$ vertices whose removal results in connected components of sizes at most $k$.
  • bounded vertex integrity does not imply bounded neighborhood diversity
  • graph class stars has unbounded vertex integrity