-

 

 

 




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

 

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