Sparse Vertex Cutsets and the Maximum Degree

We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\Big(1-\frac{1}{{r\choose 2}}\Big)\Delta+O(1)$.

Authors

Publication Details

Journal
The Electronic Journal of Combinatorics
Published
2025-05-22
DOI
https://doi.org/10.37236/12902
Primary Topic
Advanced Numerical Analysis Techniques
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Sparse Vertex Cutsets and the Maximum Degree

Dieter Rautenbach, Stéphane Bessy, Johannes Rauch, Uéverton S. Souza
The Electronic Journal of Combinatorics
Advanced Numerical Analysis Techniques
article

Sparse Vertex Cutsets and the Maximum Degree

Dieter Rautenbach, Stéphane Bessy, Johannes Rauch, Uéverton S. Souza
article en

Abstract

We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\Big(1-\frac{1}{{r\choose 2}}\Big)\Delta+O(1)$.

The Electronic Journal of CombinatoricsVol. 32(2)
Openalex Percentile: Top 88%
Advanced Numerical Analysis Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.