vertex integrity

• assumed
  • vertex integrity upper bounds distance to bounded components by a linear function – By definition
  • distance to bounded components upper bounds vertex integrity by a linear function – By definition
• unknown source
  • vertex integrity upper bounds treedepth by a linear function – First, treedepth removes vertices of the modulator, then it iterates through remaining components one by one.
  • 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