Zum Inhalt springen

Nur-Lesen-Fassung: Das Forschungsinformationssystem (FIS) ist aus Sicherheitsgründen vorübergehend durch diese Nur-Lesen-Fassung ersetzt. Alle öffentlichen Inhalte und Volltexte sind weiterhin abrufbar; Anmeldung, Bearbeitung, Einreichung und Statistiken stehen nicht zur Verfügung. Bei Fragen: fis@uni-bamberg.de

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

Publikation

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

Adler, Isolde; Köhler, Noleen (2023): An explicit construction of graphs of bounded degree that are far from being Hamiltonian, in: Bamberg: Otto-Friedrich-Universität, S. 1–19.

Details

Fakultät/Lehrstuhl
Autorin(nen)/Autor(en)
Köhler, Noleen
Verlagsangabe
Otto-Friedrich-Universität : Bamberg
Erscheinungsjahr
2023
Quelle/Weitere Ausgabe
Discrete mathematics and theoretical computer science : DMTCS, 24 (2022), 1, S. 1-19. - ISSN: 1365-8050
Jahr der Erstpublikation
2022
Sprache(n)
Englisch
Lizenz
URN
Abstract

Hamiltonian cycles in graphs were first studied in the 1850s. Since then, an impressive amount of research has been dedicated to identifying classes of graphs that allow Hamiltonian cycles, and to related questions. The corresponding decision problem, that asks whether a given graph is Hamiltonian (i.\,e.\ admits a Hamiltonian cycle), is one of Karp's famous NP-complete problems. In this paper we study graphs of bounded degree that are \emph{far} from being Hamiltonian, where a graph G on n vertices is \emph{far} from being Hamiltonian, if modifying a constant fraction of n edges is necessary to make G Hamiltonian. We give an explicit deterministic construction of a class of graphs of bounded degree that are locally Hamiltonian, but (globally) far from being Hamiltonian. Here, \emph{locally Hamiltonian} means that every subgraph induced by the neighbourhood of a small vertex set appears in some Hamiltonian graph. More precisely, we obtain graphs which differ in Θ(n) edges from any Hamiltonian graph, but non-Hamiltonicity cannot be detected in the neighbourhood of o(n) vertices. Our class of graphs yields a class of hard instances for one-sided error property testers with linear query complexity. It is known that any property tester (even with two-sided error) requires a linear number of queries to test Hamiltonicity (Yoshida, Ito, 2010). This is proved via a randomised construction of hard instances. In contrast, our construction is deterministic. So far only very few deterministic constructions of hard instances for property testing are known. We believe that our construction may lead to future insights in graph theory and towards a characterisation of the properties that are testable in the bounded-degree model.

GND-Schlagwort(e)
Diskrete Mathematik
Berechnungskomplexität
Datenstruktur
Algorithmus
Freie Schlagwort(e)
Computer Science - Discrete Mathematics
Computer Science - Computational Complexity
Computer Science - Data Structures and Algorithms,G.2.2
DDC-Klassifikation
004 Computer science
500 Naturwissenschaften
RVK-Klassifikation
SK 890
Peer Reviewed
ja
Internationale Verbreitung
ja
Open-Access-Zeitschrift
ja
Dokumenttyp
Artikel in einer Zeitschrift / Postprint
URI
Datum der Freischaltung
05.10.2023

Permalink: https://fis.uni-bamberg.de/handle/uniba/91022 · Daten als JSON · Zitieren: BibTeX · RIS

Datenstand: 15.11.2026

Eingeschränkter Lesezugriff: Anmeldung, Bearbeitung und Einreichung sind vorübergehend deaktiviert.