Publication: A counterexample to the dominating set conjecture

All || By Area || By Year

Title A counterexample to the dominating set conjecture
Authors/Editors* Antoine Deza, Gabriel Indik
Where published* Optimization Letters
How published* Journal
Year* 2007
Volume 1
Number 2
Pages 163-169
Publisher Springer
Keywords Dominating set conjecture - Metric polyhedra - Cut polyhedra
The metric polytope met_n is the polyhedron associated with all semimetrics on n nodes and defined by the triangle inequalities x_ij − x_ik − x_jk ≤ 0 and x_ij + x_ik + x_jk ≤ 2 for all triples i, j, k of {1,..., n}. In 1992 Monique Laurent and Svatopluk Poljak conjectured that every fractional vertex of the metric polytope is adjacent to some integral vertex. The conjecture holds for n ≤ 8 and, in particular, for the 1,550,825,600 vertices of met_8. While the overwhelming majority of the known vertices of met_9 satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex.
Go to High Performance Computing
Back to page 62 of list