Embedding spanning subgraphs in uniformly dense and inseparable graphs

DOI10.1002/RSA.20957MaRDI QIDQ3386528zbMATH OpenOpenAlexFDO

Authors Oliver Ebsen, Giulia S. Maesaka, Christian Reiher, M. Schacht, Bjarne Schülke

Publication date 5 January 2021

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

Full work available at URL https://arxiv.org/abs/1909.13071

zbMATH Keywords

absorption methodpowers of Hamiltonian cyclesbandwidth theorem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Eulerian and Hamiltonian graphs (05C45) Density (toughness, etc.) (05C42) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We consider sufficient conditions for the existence of $k$-th powers of Hamiltonian cycles in $n$-vertex graphs $G$ with minimum degree $mun$ for arbitrarily small $mu>0$. About 20 years ago Koml'os, Sark"ozy, and Szemer'edi resolved the conjectures of P'osa and Seymour and obtained optimal minimum degree conditions for this problem by showing that $mu=frackk+1$ suffices for large $n$. For smaller values of $mu$ the given graph $G$ must satisfy additional assumptions. We show that inducing subgraphs of density $d>0$ on linear subsets of vertices and being inseparable, in the sense that every cut has density at least $mu>0$, are sufficient assumptions for this problem and, in fact, for a variant of the bandwidth theorem. This generalises recent results of Staden and Treglown.

Recommendations

• scientific article; zbMATH DE number 1286511
• Proof of the Seymour conjecture for large graphs
• scientific article; zbMATH DE number 800446
• Counting odd cycles in locally dense graphs
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs
• scientific article; zbMATH DE number 3943849
• On a Hamiltonian cycle in which specified vertices are uniformly distributed
• scientific article; zbMATH DE number 861428
• A chvátal–erdős type condition for hamiltonian graphs
• Cycles through prescribed vertices with large degree sum

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Blow-up lemma
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• On the maximal number of independent circuits in a graph
• Proof of the Seymour conjecture for large graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Some Theorems on Abstract Graphs
• Squares of Hamiltonian cycles in 3-uniform hypergraphs
• The Blow-up Lemma
• The Ramsey number of a graph with bounded maximum degree
• The bandwidth theorem for locally dense graphs
• Triangle factors of graphs without large independent sets and of weighted graphs

Cited in

(8)

• Embedding spanning subgraphs of small bandwidth
• EMBEDDING SPANNING BOUNDED DEGREE GRAPHS IN RANDOMLY PERTURBED GRAPHS
• The bandwidth theorem for locally dense graphs
• Powers of Hamiltonian cycles in \(\mu\)-inseparable graphs
• Sufficient conditions for perfect mixed tilings
• On sufficient conditions for spanning structures in dense graphs
• On embedding well-separable graphs
• Minimum Degrees for Powers of Paths and Cycles

This page was built for publication: Embedding spanning subgraphs in uniformly dense and inseparable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386528)