Using Integer Programming to Search for Counterexamples: A Case Study

Autor:	Giuseppe Lancia, Franca Rinaldi, Eleonora Pippia
Rok vydání:	2020
Předmět:	Combinatorics Conjecture Integer programming Graph Hamiltonian (control theory) Mathematics Counterexample
Zdroj:	Mathematical Optimization Theory and Operations Research ISBN: 9783030499877 MOTOR
DOI:	10.1007/978-3-030-49988-4_5
Popis:	It is known that there exist 4-regular, 1-tough graphs which are non-hamiltonian. The smallest such graph known has \(n=18\) nodes and was found by Bauer et al., who conjectured that all 4-regular, 1-tough graphs with \(n\le 17\) are hamiltonian. They in fact proved that this is true for \(n\le 15\), but left open the possibility of non-hamiltonian graphs of 16 or 17 nodes. By using ILP for modeling a counterexample, and then finding out that the model has no solutions, we give an algorithmic proof that their conjecture was indeed correct.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::4c4ca9d1d22b3a18ffd609ab2190f98b https://doi.org/10.1007/978-3-030-49988-4_5 Zobrazit plný text záznamu