Number of the records: 1
On sufficient conditions for spanning structures in dense graphs
- 1.
SYSNO ASEP 0573793 Document Type V - Research Report R&D Document Type The record was not marked in the RIV Title On sufficient conditions for spanning structures in dense graphs Author(s) Lang, R. (DE)
Sanhueza-Matamala, Nicolás (UIVT-O) SAINumber of authors 2 Issue data Cornell University: Cornell University, 2023 Series arXiv.org e-Print archive Series number arXiv:2110.14547 Number of pages 68 s. Publication form Online - E Language eng - English Country US - United States R&D Projects GA19-08740S GA ČR - Czech Science Foundation (CSF) Institutional support UIVT-O - RVO:67985807 DOI 10.48550/arXiv.2110.14547 Annotation We study structural conditions in dense graphs that guarantee the existence of vertex-spanning substructures such as Hamilton cycles. It is easy to see that every Hamiltonian graph is connected, has a perfect fractional matching and, excluding the bipartite case, contains an odd cycle. A simple consequence of the Robust Expander Theorem of Kühn, Osthus and Treglown tells us that any large enough graph that robustly satisfies these properties must already be Hamiltonian. Our main result generalises this phenomenon to powers of cycles and graphs of sublinear bandwidth subject to natural generalisations of connectivity, matchings and odd cycles.
This answers a question of Ebsen, Maesaka, Reiher, Schacht and Schülke and solves the embedding problem that underlies multiple lines of research on sufficient conditions for spanning structures in dense graphs. As applications, we recover and establish Bandwidth Theorems in a variety of settings including Ore-type degree conditions, Pósa-type degree conditions, deficiency-type conditions, locally dense and inseparable graphs, multipartite graphs as well as robust expanders.Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2024
Number of the records: 1