Separating Matchings in Cubic Graphs
We study separating matchings in graphs, that is, matchings whose removal increases the number of connected components, and focus on determining the maximum size of such a matching in a graph $G$, denoted by $\mathrm{mms}(G)$. We show that every subcubic graph admits a separating matching, except for exactly eight graphs, which allows us to focus on bounding $\mathrm{mms}(G)$ for cubic graphs. Our main results show that every cubic graph $G$ on $n$ vertices that admits a separating matching satisfies $\mathrm{mms}(G) \ge n/2 - 2$. For bipartite cubic graphs, assuming a conjecture of Funk,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.17226
curl -X POST /api/v1/records/arxiv/2604.17226/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.17226/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'