Optimization Online


A counterexample to the dominating set conjecture

Antoine Deza (deza***at***mcmaster.ca)
Gabriel Indik (indikg***at***mcmaster.ca)

Abstract: The metric polytope m(n) is the polyhedron associated with all semimetrics on n nodes. 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<9 and, in particular, for the 1 550 825 600 vertices of m(8). While the overwhelming majority of the known vertices of m(9) satisfy the conjecture, we exhibit a fractional vertex not adjacent to any integral vertex.

Keywords: Dominating Set Conjecture, Metric polyhedra, Cut polyhedra

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Citation: AdvOL-Report 2005/21, McMaster University, Hamilton, Ontario, Canada (November 2005)

Download: [PDF]

Entry Submitted: 12/21/2005
Entry Accepted: 12/21/2005
Entry Last Modified: 04/01/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society