maximum leaf number
tags: covering vertices
equivalent to: maximum leaf number
providers: ISGCI
Relations
Other | Relation from | Relation to |
---|---|---|
acyclic chromatic number | exclusion | upper bound |
arboricity | exclusion | upper bound |
average degree | exclusion | upper bound |
average distance | exclusion | exclusion |
bandwidth | exclusion | upper bound |
bipartite | unbounded | unknown to HOPS |
bipartite number | exclusion | unknown to HOPS |
bisection bandwidth | exclusion | upper bound |
block | unbounded | unknown to HOPS |
book thickness | exclusion | upper bound |
boolean width | exclusion | upper bound |
bounded components | exclusion | exclusion |
boxicity | exclusion | upper bound |
branch width | exclusion | upper bound |
c-closure | exclusion | upper bound |
carving-width | exclusion | upper bound |
chordal | unbounded | unknown to HOPS |
chordality | exclusion | upper bound |
chromatic number | exclusion | upper bound |
clique cover number | exclusion | exclusion |
clique-tree-width | exclusion | upper bound |
clique-width | exclusion | upper bound |
cluster | unbounded | exclusion |
co-cluster | unbounded | exclusion |
cograph | unbounded | exclusion |
complete | unbounded | exclusion |
connected | unbounded | unknown to HOPS |
cutwidth | exclusion | upper bound |
cycle | constant | unknown to HOPS |
cycles | unbounded | unknown to HOPS |
d-path-free | exclusion | exclusion |
degeneracy | exclusion | upper bound |
degree treewidth | exclusion | upper bound |
diameter | exclusion | exclusion |
diameter+max degree | exclusion | exclusion |
disjoint cycles | unbounded | unknown to HOPS |
distance to bipartite | exclusion | upper bound |
distance to block | exclusion | upper bound |
distance to bounded components | exclusion | exclusion |
distance to chordal | exclusion | upper bound |
distance to cluster | exclusion | unknown to HOPS |
distance to co-cluster | exclusion | exclusion |
distance to cograph | exclusion | exclusion |
distance to complete | exclusion | exclusion |
distance to edgeless | exclusion | exclusion |
distance to forest | exclusion | upper bound |
distance to interval | exclusion | upper bound |
distance to linear forest | exclusion | upper bound |
distance to maximum degree | exclusion | upper bound |
distance to outerplanar | exclusion | upper bound |
distance to perfect | exclusion | upper bound |
distance to planar | exclusion | upper bound |
distance to stars | exclusion | exclusion |
domatic number | exclusion | upper bound |
domination number | exclusion | exclusion |
edge clique cover number | exclusion | exclusion |
edge connectivity | exclusion | upper bound |
edgeless | unknown to HOPS | exclusion |
feedback edge set | exclusion | upper bound |
feedback vertex set | exclusion | upper bound |
forest | unbounded | unknown to HOPS |
genus | exclusion | upper bound |
girth | exclusion | exclusion |
grid | unbounded | unknown to HOPS |
h-index | exclusion | upper bound |
inf-flip-width | exclusion | upper bound |
interval | unbounded | unknown to HOPS |
iterated type partitions | exclusion | exclusion |
linear clique-width | exclusion | upper bound |
linear forest | unknown to HOPS | unknown to HOPS |
linear NLC-width | exclusion | upper bound |
linear rank-width | exclusion | upper bound |
maximum clique | exclusion | upper bound |
maximum degree | exclusion | upper bound |
maximum independent set | exclusion | exclusion |
maximum induced matching | exclusion | exclusion |
maximum matching | exclusion | exclusion |
maximum matching on bipartite graphs | exclusion | exclusion |
mim-width | exclusion | upper bound |
minimum degree | exclusion | upper bound |
mm-width | exclusion | upper bound |
modular-width | exclusion | exclusion |
module-width | exclusion | upper bound |
neighborhood diversity | exclusion | exclusion |
NLC-width | exclusion | upper bound |
NLCT-width | exclusion | upper bound |
odd cycle transversal | exclusion | upper bound |
outerplanar | unbounded | unknown to HOPS |
path | unknown to HOPS | unknown to HOPS |
pathwidth | exclusion | upper bound |
pathwidth+maxdegree | exclusion | upper bound |
perfect | unbounded | unknown to HOPS |
planar | unbounded | unknown to HOPS |
radius-r flip-width | exclusion | upper bound |
rank-width | exclusion | upper bound |
shrub-depth | exclusion | unknown to HOPS |
sim-width | exclusion | upper bound |
star | unbounded | exclusion |
stars | unbounded | exclusion |
topological bandwidth | exclusion | upper bound |
tree | unbounded | unknown to HOPS |
tree-independence number | exclusion | upper bound |
treedepth | exclusion | exclusion |
treelength | exclusion | unknown to HOPS |
treewidth | exclusion | upper bound |
twin-cover number | exclusion | exclusion |
twin-width | exclusion | upper bound |
vertex connectivity | exclusion | unknown to HOPS |
vertex cover | exclusion | exclusion |
vertex integrity | exclusion | exclusion |
Results
- 2019 The Graph Parameter Hierarchy by Sorge
- page 8 : maximum leaf number upper bounds distance to linear forest by a linear function – Lemma 4.10 ([14]). The max-leaf number $\mathrm{ml}$ upper bounds the distance to disjoint paths $d$. We have $d \le \mathrm{ml}-1$.
- page 10 : maximum leaf number upper bounds bandwidth by a linear function – Lemma 4.25. The max leaf number $\mathrm{ml}$ strictly upper bounds the bandwidth $\mathrm{bw}$.
- Comparing Graph Parameters by Schröder
- page 21 : bounded maximum leaf number does not imply bounded girth – Proposition 3.14
- https://mathworld.wolfram.com/MaximumLeafNumber.html
- maximum leaf number – … the largest number of tree leaves in any of its spanning trees.
- unknown source
- maximum leaf number upper bounds distance to linear forest by a computable function
- maximum leaf number upper bounds feedback edge set by a computable function
- graph class cycle has constant maximum leaf number
- maximum leaf number upper bounds feedback edge set by a polynomial function – M. Bentert (personal communication)