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}$, $Prism_7, APrism_6$, M\"{ o}bius ladder $M_{ 14}$, Dodecahedron, Heawood and Petersen graphs. For $K_8$, it shows that the huge lists of facets of the cut polytope $CUTP_8$ and cut cone $CUT_8$, given in [CR] is complete. We also confirm the conjecture that any facet of $CUTP_8$ 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 (see, for example, [Werner]) in quantum information theory.

Categories: math.CO math.MG

Enumeration of the facets of cut polytopes over some highly symmetric graphs