The minimum degree of minimally k-extendable graphs for some k
Source: arxiv.org/abs/2611.22690
A graph on at least 2k+2 vertices is k-extendable if every matching of size k extends to a perfect matching, and it is minimally k-extendable if it is k-extendable but deleting any edge is not. Plummer proved that every k-extendable graph is (k+1)-connected. So its minimum degree is at least k+1. Lou and Yu conjectured that a minimally k-extendable graph on at most 4k vertices has minimum degree in {k+1,2k,2k+1}; the case k=1 and the claw-free case of k=2 have been settled previously. We determine the minimum degree of minimally k-extendable graphs for k=2 and k=3, thereby settling the…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.22690
curl -X POST /api/v1/records/arxiv/2611.22690/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.22690/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'