Dirac's theorem for graphs of bounded bandwidth

Diaz, A. E., Gupta, P., Cecchelli, D. M., Parczyk, O. & Sgueglia, A. (2026). Dirac's theorem for graphs of bounded bandwidth. Electronic Journal of Combinatorics, 33(1). https://doi.org/10.37236/13474
Copy

Abstract

We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph K2,ℓ. This includes the containment of Hamilton paths and cycles, and has applications in the random geometric graph model. Our proof provides a greedy algorithm for constructing such structures.
Item Type Article
Copyright holders © The authors
Departments LSE > Academic Departments > Mathematics
DOI 10.37236/13474
Date Deposited 10 February 2026
Acceptance Date 13 October 2025
URI https://researchonline.lse.ac.uk/id/eprint/137168

Explore Further

picture_as_pdf
subject
Published Version
Creative Commons: Attribution 4.0
Download

EndNote BibTeX Reference Manager (RIS) Refer Atom Dublin Core JSON Multiline CSV OPENAIRE
Export

Downloads
View more statistics