Enumeration of the facets of cut polytopes over some highly symmetric graphs. (30th July 2015)

• Record Type: Journal Article
• Authors: Deza, Michel; Dutour Sikirić, Mathieu
• Other Names: Lavor Carlile guestEditor.; Firer Marcelo guestEditor.; Martínez José Mario guestEditor.; Liberti Leo guestEditor.
• Is Part Of: International transactions in operational research. Volume 23:Number 5(2016:Sep.)
• Page Start: 853
• Page End: 860
• Publication Date: 2015-07-30
• Subjects: enumeration -- graph theory -- polyhedra -- branch and bound -- combinatorial optimization; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12194
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: We report here a computation giving the complete list of facets for the cut polytopes over several very symmetric graphs with 15–30 edges, including K 8, K 3, 3, 3, K 1, 4, 4, K 5, 5, some other K l, m, K 1, l, m, P r i s m 7, A P r i s m 6, Möbius ladder M 14, dodecahedron, Heawood, and Petersen graphs. For K 8, it shows that the huge list of facets of the cut polytope CUTP8 and cut cone CUT8, given in the literature is complete. We also confirm the conjecture that any facet of CUTP8 is adjacent to a triangle facet. The lists of facets for K 1, l, m with ( l, m ) = ( 4, 4 ), ( 3, 5 ), ( 3, 4 ) solve problems in the quantum information theory.