Nearly-uniform degree distributions in spanning subgraphs
We show that, when $d=o(n)$, every $d$-regular $n$-vertex graph contains a spanning subgraph whose degree distribution is nearly uniform, i.e., for each $0\leq i\leq d$, there are $(1+o(1))n/(d+1)$ vertices with degree $i$. This proves a conjecture of Alon and Wei on irregular subgraphs and strengthens a previous result of Fox, Luo and Pham.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.30612
curl -X POST /api/v1/records/arxiv/2606.30612/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.30612/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'