Abstract:We study matching-removability under the degree/connectivity regime of Halin's theorem, which asserts that every $k$-connected graph $G$ with minimum degree $\delta(G)\ge k+1$ contains an edge $e$ such that $G-e$ remains $k$-connected. For $k,\ell\ge 1$, an $\ell$-matching is a matching of size $\ell$. A matching $M$ in a $k$-connected graph $G$ is {\it $k$-removable} if $G-M$ remains $k$-connected. We improve Halin's result by proving that every $k$-connected graph $G$ with $\delta(G)\ge k+1$ contains a $k$-removable $2$-matching, except when $k=1$ and $G$ is a cycle. For small $k$ we obtain stronger bounds: (i) $k=1$: a 1-removable $\min\{\lfloor n/2\rfloor,\delta(G)\}$-matching; (ii) $k=2$: a 2-removable $\lceil(\delta(G)+1)/2\rceil$-matching, with a unique tight exception when $\delta(G)$ is even and $G\cong K_{\delta(G)+1}$; and (iii) $k=3$: for $\delta(G)\ge 5$, a $3$-removable $\lceil(\delta(G)+1)/2\rceil$-matching. All these bounds are optimal with respect to removable matching size and minimum degree.
We also show that for every $n\ge 2\delta$, there exists a $k$-connected $n$-vertex graph $G$ with minimum degree $\delta$ that does not contain a $k$-removable matching of size at least $\delta(G)+1$. Moreover, for $k\le 2$ there exists a $k$-removable $(\delta(G)-c)$-matching for some $c\le 3$, which is optimal up to the additive constant.
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05C40, 05C70 |
| Cite as: | arXiv:2605.24035 [math.CO] |
| (or arXiv:2605.24035v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.24035 arXiv-issued DOI via DataCite (pending registration) |
From: Hengzhe Li [view email]
[v1]
Thu, 21 May 2026 08:35:14 UTC (15 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。