PreprintCC BY 4.0arXiv
Nearly Spanning Regular Subgraphs
Abstract
Alon and Mubayi asked whether, for every integer k≥1 and every ε>0, there exists r0=r0(k,ε) such that every r-regular graph on n vertices with r≥ r0 contains a k-regular subgraph covering at least (1−ε)n vertices. Previously, the conjecture was known for k∈{1,2} and for k and r both even. We answer this question affirmatively for general k and r with ε=Ok(r−1/2). For k=2 and every odd r≥3, we show that ε=1/(r2−3) suffices which is best possible.
Related
- Local Resilience for Containment of Bounded Degree Spanning Subgraphs
- A sharp upper bound on the number of spanning forests of regular graphs
- Nearly Lefschetz fibrations, Stein structures, and regular Lagrangians
- Note on near-spanning balanced antidirected trees missing from regular tournaments
- Large induced subgraphs with k vertices of maximum degree
BibTeX
@misc{sivashankar2026nearly,
title = {{Nearly Spanning Regular Subgraphs}},
author = {Varun Sivashankar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19777},
eprint = {2609.19777},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19777},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nearly Spanning Regular Subgraphs
AU - Varun Sivashankar
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2609.19777
UR - https://arxiv.org/abs/2609.19777
AB - Alon and Mubayi asked whether, for every integer k≥1 and every ε>0, there exists r_0=r_0(k,ε) such that every r-regular graph on n vertices with r≥ r_0 contains a k-regular subgraph covering at least (1−ε)n vertices. Previously, the conjecture was known for k∈{1,2} and for k and r both even. We answer this question affirmatively for general k and r with ε=O_k(r^−1/2). For k=2 and every odd r≥3, we show that ε=1/(r^2−3) suffices which is best possible.
ER -