diameter
- assumed
- diameter upper bounds average distance by a linear function – By definition
- unknown source
- domination number upper bounds diameter by a linear function – 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 upper bounds diameter by a computable function
- maximum induced matching upper bounds diameter by a linear function – Diameter requires an induced path on $d$ edges, hence, maximum induced matching is at least $\lfloor (d+1)/3 \rfloor$.
- modular-width upper bounds diameter by a computable function
- diameter – Maximum distance of two vertices that are in the same connected component.
- graph class path has unbounded diameter – trivially
- Tran2022
- page 25 : modular-width upper bounds diameter by a linear function – 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.
- https://en.wikipedia.org/wiki/Distance_(graph_theory)#Related_concepts
- diameter – … [diameter] is the greatest distance between any pair of vertices …
- SchroderThesis