maximum degree
providers: ISGCI
Definition: Maximum degree over graph’s vertices.
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 | ■ | upper bound | exclusion |
bipartite | ■ | unbounded | exclusion |
bipartite number | ■ | exclusion | unknown to HOPS |
bisection bandwidth | ■ | exclusion | exclusion |
block | ■ | unbounded | exclusion |
book thickness | ■ | exclusion | unknown to HOPS |
boolean width | ■ | exclusion | exclusion |
bounded components | ■ | upper bound | exclusion |
boxicity | ■ | exclusion | upper bound |
branch width | ■ | exclusion | exclusion |
c-closure | ■ | exclusion | upper bound |
carving-width | ■ | upper bound | exclusion |
chordal | ■ | unbounded | exclusion |
chordality | ■ | exclusion | upper bound |
chromatic number | ■ | exclusion | upper bound |
clique cover number | ■ | exclusion | exclusion |
clique-tree-width | ■ | exclusion | exclusion |
clique-width | ■ | exclusion | exclusion |
cluster | ■ | unbounded | exclusion |
co-cluster | ■ | unbounded | exclusion |
cograph | ■ | unbounded | exclusion |
complete | ■ | unbounded | exclusion |
connected | ■ | unbounded | exclusion |
contraction complexity | ■ | upper bound | exclusion |
cutwidth | ■ | upper bound | exclusion |
cycle | ■ | upper bound | exclusion |
cycles | ■ | upper bound | exclusion |
d-path-free | ■ | exclusion | exclusion |
degeneracy | ■ | exclusion | upper bound |
degree treewidth | ■ | upper bound | exclusion |
diameter | ■ | exclusion | exclusion |
diameter+max degree | ■ | upper bound | exclusion |
disconnected | ■ | unknown to HOPS | unknown to HOPS |
disjoint cycles | ■ | unbounded | exclusion |
distance to bipartite | ■ | exclusion | exclusion |
distance to block | ■ | exclusion | exclusion |
distance to bounded components | ■ | exclusion | exclusion |
distance to chordal | ■ | exclusion | exclusion |
distance to cluster | ■ | exclusion | exclusion |
distance to co-cluster | ■ | exclusion | exclusion |
distance to cograph | ■ | exclusion | exclusion |
distance to complete | ■ | exclusion | exclusion |
distance to disconnected | ■ | exclusion | upper bound |
distance to edgeless | ■ | exclusion | exclusion |
distance to forest | ■ | exclusion | exclusion |
distance to interval | ■ | exclusion | exclusion |
distance to linear forest | ■ | exclusion | exclusion |
distance to maximum degree | ■ | exclusion | upper bound |
distance to outerplanar | ■ | exclusion | exclusion |
distance to perfect | ■ | exclusion | exclusion |
distance to planar | ■ | exclusion | exclusion |
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 | ■ | upper bound | exclusion |
feedback edge set | ■ | exclusion | exclusion |
feedback vertex set | ■ | exclusion | exclusion |
forest | ■ | unbounded | exclusion |
genus | ■ | exclusion | exclusion |
girth | ■ | exclusion | exclusion |
grid | ■ | upper bound | exclusion |
h-index | ■ | exclusion | upper bound |
inf-flip-width | ■ | exclusion | exclusion |
interval | ■ | unbounded | exclusion |
iterated type partitions | ■ | exclusion | exclusion |
linear clique-width | ■ | exclusion | exclusion |
linear forest | ■ | upper bound | exclusion |
linear NLC-width | ■ | exclusion | exclusion |
linear rank-width | ■ | exclusion | exclusion |
maximum clique | ■ | exclusion | upper bound |
maximum degree | ■ | equal | equal |
maximum independent set | ■ | exclusion | exclusion |
maximum induced matching | ■ | exclusion | exclusion |
maximum leaf number | ■ | upper bound | exclusion |
maximum matching | ■ | exclusion | exclusion |
maximum matching on bipartite graphs | ■ | exclusion | exclusion |
mim-width | ■ | exclusion | unknown to HOPS |
minimum degree | ■ | exclusion | upper bound |
mm-width | ■ | exclusion | exclusion |
modular-width | ■ | exclusion | exclusion |
module-width | ■ | exclusion | exclusion |
neighborhood diversity | ■ | exclusion | exclusion |
NLC-width | ■ | exclusion | exclusion |
NLCT-width | ■ | exclusion | exclusion |
odd cycle transversal | ■ | exclusion | exclusion |
outerplanar | ■ | unbounded | exclusion |
path | ■ | upper bound | exclusion |
pathwidth | ■ | exclusion | exclusion |
pathwidth+maxdegree | ■ | upper bound | exclusion |
perfect | ■ | unbounded | exclusion |
planar | ■ | unbounded | exclusion |
radius-r flip-width | ■ | exclusion | unknown to HOPS |
rank-width | ■ | exclusion | exclusion |
shrub-depth | ■ | exclusion | exclusion |
sim-width | ■ | exclusion | unknown to HOPS |
size | ■ | upper bound | exclusion |
star | ■ | unbounded | exclusion |
stars | ■ | unbounded | exclusion |
topological bandwidth | ■ | unknown to HOPS | exclusion |
tree | ■ | unbounded | exclusion |
tree-independence number | ■ | exclusion | unknown to HOPS |
treedepth | ■ | exclusion | exclusion |
treelength | ■ | exclusion | unknown to HOPS |
treewidth | ■ | exclusion | exclusion |
twin-cover number | ■ | exclusion | exclusion |
twin-width | ■ | exclusion | exclusion |
vertex connectivity | ■ | exclusion | upper bound |
vertex cover | ■ | exclusion | exclusion |
vertex integrity | ■ | exclusion | exclusion |
Results
- 2022 Expanding the Graph Parameter Hierarchy by Tran
- page 32 : maximum degree upper bounds c-closure by a computable function – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
- page 32 : bounded c-closure does not imply bounded maximum degree – Proposition 5.1. Maximum Degree strictly upper bounds $c$-Closure.
- page 40 : bounded twin-width does not imply bounded maximum degree – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
- page 40 : bounded maximum degree does not imply bounded twin-width – Proposition 6.8. Twin-width is incomparable to Maximum Degree.
- 2019 The Graph Parameter Hierarchy by Sorge
- page 8 : maximum degree upper bounds acyclic chromatic number by a polynomial function – Lemma 4.6 ([15]). The acyclic chromatic number $\chi_a$ is uppre bounded by the maximum degree $\Delta$ (for every graph with $\Delta > 4$). We have $\chi_a \le \Delta(\Delta-1)/2$.
- 2013 Characterizing graphs of small carving-width by Belmonte, van ’t Hof, Kamiński, Paulusma, Thilikos
- carving-width upper bounds maximum degree by a linear function – Observation 1. Let $G$ be a graph. Then $cw(G) \ge \Delta(G)$.
- 2010 Comparing 17 graph parameters by Sasák
- page 28 : cutwidth upper bounds maximum degree by a linear function – Lemma 2.18. For any graph $G$ and any vertex $v \in V(G), cutw(g) \ge \lceil \frac{deg(v)}2 \rceil$.
- page 30 : carving-width upper bounds maximum degree by a linear function – Lemma 2.20 Carving-width of a graph $G$ is at least $\Delta(G)$ where $\Delta(G)$ is the maximum degree of a graph $G$.
- 2008 Simulating Quantum Computation by Contracting Tensor Networks by Markov, Shi
- page 10 : contraction complexity upper bounds maximum degree by a linear function – $cc(G) \ge \Delta(G) - 1$
- unknown source
- maximum degree upper bounds h-index by a linear function – As h-index seeks $k$ vertices of degree $k$ it is trivially upper bound by maximum degree.
- bandwidth upper bounds maximum degree by a linear function – Each vertex has an integer $i$ and may be connected only to vertices whose difference from $i$ is at most $k$. There are at most $k$ bigger and $k$ smaller such neighbors.
- maximum degree upper bounds c-closure by a computable function
- grid upper bounds maximum degree by a constant
- graph class planar has unbounded maximum degree
- graph class star has unbounded maximum degree – trivially
- Comparing Graph Parameters by Schröder
- page 24 : bounded vertex cover does not imply bounded maximum degree – Proposition 3.19
- page 28 : bounded maximum degree does not imply bounded clique-width – Proposition 3.26
- page 28 : bounded maximum degree does not imply bounded bisection bandwidth – Proposition 3.26
- assumed
- pathwidth+maxdegree upper bounds maximum degree by a linear function – by definition
- degree treewidth upper bounds maximum degree by a linear function – by definition
- maximum degree upper bounds distance to maximum degree by a linear function – by definition
- diameter+max degree upper bounds maximum degree by a linear function – by definition
- grid upper bounds maximum degree by a constant – By definition
- bounded components upper bounds maximum degree by a linear function – By definition
- linear forest upper bounds maximum degree by a constant – By definition
- cycles upper bounds maximum degree by a constant – By definition
- maximum degree is equivalent to maximum degree – assumed