From Halin's Edge Removability to Matching Removability in $k$-Connected Graphs
We study matching-removability under the degree/connectivity regime of Halin's theorem, which asserts that every $k$-connected graph $G$ with minimum degree $δ(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 $δ(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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.24035
curl -X POST /api/v1/records/arxiv/2605.24035/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.24035/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'