Geodesic
Sparse vertex cutsets and the maximum degree
The electronic journal of combinatorics, Tome 32 (2025) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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)$.
DOI : 10.37236/12902
Classification : 05C07, 05C35
Mots-clés : 5-regular connected graph, induced subgraph 
@article{10_37236_12902,
     author = {St\'ephane  Bessy and Johannes Rauch and Dieter Rautenbach and U\'everton S.  Souza},
     title = {Sparse vertex cutsets and the maximum degree},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {2},
     doi = {10.37236/12902},
     zbl = {1565.05020},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12902/}
}
TY  - JOUR
AU  - Stéphane  Bessy
AU  - Johannes Rauch
AU  - Dieter Rautenbach
AU  - Uéverton S.  Souza
TI  - Sparse vertex cutsets and the maximum degree
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12902/
DO  - 10.37236/12902
ID  - 10_37236_12902
ER  - 
%0 Journal Article
%A Stéphane  Bessy
%A Johannes Rauch
%A Dieter Rautenbach
%A Uéverton S.  Souza
%T Sparse vertex cutsets and the maximum degree
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12902/
%R 10.37236/12902
%F 10_37236_12902
Stéphane  Bessy; Johannes Rauch; Dieter Rautenbach; Uéverton S.  Souza. Sparse vertex cutsets and the maximum degree. The electronic journal of combinatorics, Tome 32 (2025) no. 2. doi: 10.37236/12902

Cité par Sources :