diameter

equivalent to: diameter

providers: ISGCI

Relations

Other	Relation from	Relation to
acyclic chromatic number	exclusion	exclusion
arboricity	exclusion	exclusion
average degree	exclusion	exclusion
average distance	unknown to HOPS	upper bound
bandwidth	exclusion	exclusion
bipartite	unbounded	exclusion
bipartite number	unknown to HOPS	upper bound
bisection bandwidth	exclusion	exclusion
block	unbounded	exclusion
book thickness	exclusion	exclusion
boolean width	exclusion	exclusion
bounded components	upper bound	exclusion
boxicity	exclusion	exclusion
branch width	exclusion	exclusion
c-closure	exclusion	exclusion
carving-width	exclusion	exclusion
chordal	unbounded	exclusion
chordality	exclusion	exclusion
chromatic number	exclusion	exclusion
clique cover number	upper bound	exclusion
clique-tree-width	exclusion	exclusion
clique-width	exclusion	exclusion
cluster	constant	exclusion
co-cluster	constant	exclusion
cograph	constant	exclusion
complete	constant	exclusion
connected	unbounded	unknown to HOPS
cutwidth	exclusion	exclusion
cycle	unbounded	exclusion
cycles	unbounded	exclusion
d-path-free	upper bound	exclusion
degeneracy	exclusion	exclusion
degree treewidth	exclusion	exclusion
diameter+max degree	upper bound	exclusion
disjoint cycles	unbounded	exclusion
distance to bipartite	exclusion	exclusion
distance to block	exclusion	exclusion
distance to bounded components	upper bound	exclusion
distance to chordal	exclusion	exclusion
distance to cluster	unknown to HOPS	exclusion
distance to co-cluster	upper bound	exclusion
distance to cograph	upper bound	exclusion
distance to complete	upper bound	exclusion
distance to edgeless	upper bound	exclusion
distance to forest	exclusion	exclusion
distance to interval	exclusion	exclusion
distance to linear forest	exclusion	exclusion
distance to maximum degree	exclusion	exclusion
distance to outerplanar	exclusion	exclusion
distance to perfect	exclusion	exclusion
distance to planar	exclusion	exclusion
distance to stars	upper bound	exclusion
domatic number	exclusion	exclusion
domination number	upper bound	exclusion
edge clique cover number	upper bound	exclusion
edge connectivity	exclusion	exclusion
edgeless	constant	exclusion
feedback edge set	exclusion	exclusion
feedback vertex set	exclusion	exclusion
forest	unbounded	exclusion
genus	exclusion	exclusion
girth	unknown to HOPS	upper bound
grid	unbounded	exclusion
h-index	exclusion	exclusion
inf-flip-width	exclusion	exclusion
interval	unbounded	exclusion
iterated type partitions	upper bound	exclusion
linear clique-width	exclusion	exclusion
linear forest	unbounded	exclusion
linear NLC-width	exclusion	exclusion
linear rank-width	exclusion	exclusion
maximum clique	exclusion	exclusion
maximum degree	exclusion	exclusion
maximum independent set	upper bound	exclusion
maximum induced matching	upper bound	unknown to HOPS
maximum leaf number	exclusion	exclusion
maximum matching	upper bound	exclusion
maximum matching on bipartite graphs	upper bound	exclusion
mim-width	exclusion	unknown to HOPS
minimum degree	exclusion	exclusion
mm-width	exclusion	exclusion
modular-width	upper bound	exclusion
module-width	exclusion	exclusion
neighborhood diversity	upper bound	exclusion
NLC-width	exclusion	exclusion
NLCT-width	exclusion	exclusion
odd cycle transversal	exclusion	exclusion
outerplanar	unbounded	exclusion
path	unbounded	exclusion
pathwidth	exclusion	exclusion
pathwidth+maxdegree	exclusion	exclusion
perfect	unbounded	exclusion
planar	unbounded	exclusion
radius-r flip-width	exclusion	unknown to HOPS
rank-width	exclusion	exclusion
shrub-depth	unknown to HOPS	exclusion
sim-width	exclusion	unknown to HOPS
star	constant	exclusion
stars	constant	exclusion
topological bandwidth	exclusion	exclusion
tree	unbounded	exclusion
tree-independence number	exclusion	unknown to HOPS
treedepth	upper bound	exclusion
treelength	unknown to HOPS	upper bound
treewidth	exclusion	exclusion
twin-cover number	upper bound	exclusion
twin-width	exclusion	exclusion
vertex connectivity	unknown to HOPS	exclusion
vertex cover	upper bound	exclusion
vertex integrity	upper bound	exclusion

Results

2022 Expanding the Graph Parameter Hierarchy by Tran
- 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.
Comparing Graph Parameters by Schröder
- page 11 : treedepth upper bounds diameter by an exponential function – Proposition 3.1
https://en.wikipedia.org/wiki/Distance_(graph_theory)#Related_concepts
- diameter – … [diameter] is the greatest distance between any pair of vertices …
assumed
- diameter upper bounds average distance by a linear function – By definition
- diameter upper bounds treelength by a linear function – By definition
- diameter+max degree upper bounds diameter 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 linear 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