Embedding spanning subgraphs in uniformly dense and inseparable graphs

DOI10.1002/RSA.20957zbMATH Open1457.05059arXiv1909.13071OpenAlexW3080664976MaRDI QIDQ3386528FDOQ3386528

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)

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.

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

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

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)

Cites Work

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

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
• Minimum Degrees for Powers of Paths and Cycles
• On embedding well-separable graphs

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)