diameter

• 2022/09 Tran2022
  • page 25 : modular-width $k$ upper bounds diameter by $\mathcal O(k)$ – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
  • page 25 : bounded diameter does not imply bounded modular-width – Theorem 4.7. Modular-width strictly upper bounds Max Diameter of Components.
• SchroderThesis
  • page 11 : treedepth $k$ upper bounds diameter by $\mathcal O(k)$ – Proposition 3.1
• unknown
  • domination number $k$ upper bounds diameter by $\mathcal O(k)$ – An unbounded diameter implies a long path where no vertices that are more than $3$ apart may be dominated by the same dominating vertex, otherwise we could shorten the path. Hence, the number of dominating vertices is also unbounded.
  • distance to cograph $k$ upper bounds diameter by $f(k)$
  • maximum induced matching $k$ upper bounds diameter by $\mathcal O(k)$ – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
  • modular-width $k$ upper bounds diameter by $f(k)$
  • diameter $k$ upper bounds average distance by $\mathcal O(k)$ – By definition
  • diameter – Maximum distance of two vertices that are in the same connected component.
  • treedepth $k$ upper bounds diameter by $f(k)$ – An unbounded diameter implies the class contains paths as subgraphs. Minimum treedepth to embed a path of length $n$ in a treedepth tree is $\log n$.
• https://en.wikipedia.org/wiki/Distance_(graph_theory)#Related_concepts
  • diameter – … [diameter] is the greatest distance between any pair of vertices …