An explicit construction of graphs of bounded degree that are far from being Hamiltonian

DOI10.46298/dmtcs.7109zbMath1490.05145arXiv2008.05801OpenAlexW3124915618MaRDI QIDQ5864726

Noleen Köhler, Isolde Adler

Publication date: 8 June 2022

Published in: Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

lower boundHamiltonian cycleproperty testingbounded-degree graphsbounded-degree model

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An optimal construction of Hanf sentences
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Every minor-closed property of sparse graphs is testable
• The hamiltonicity of swapped (OTIS) networks built of Hamiltonian component networks
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• On monadic NP vs monadic co-NP
• A sublinear bipartiteness tester for bounded degree graphs
• On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
• Property testing on \(k\)-vertex-connectivity of graphs
• Every Property of Hyperfinite Graphs Is Testable
• On Proximity-Oblivious Testing
• Property testing and its connection to learning and approximation
• Expander graphs and their applications
• Updating the hamiltonian problem—A survey
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Almost all regular graphs are hamiltonian
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Robust Characterizations of Polynomials with Applications to Program Testing
• Reducibility among Combinatorial Problems
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Local Graph Partitions for Approximation and Testing
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Random walks and forbidden minors II
• Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
• Relating two property testing models for bounded degree directed graphs
• Introduction to Property Testing
• Testing subdivision-freeness
• Some Theorems on Abstract Graphs
• Efficient testing of large graphs
• Property testing in bounded degree graphs