Half-integrality of vertices of the generalized transitive tournament polytope (n=6) Original Research Article

A generalized transitive tournament matrix of order n (GTT(n) matrix) is a non-negative matrix {xij}i,j=1n such that xii=0,xij+xji=1 (i≠j), 1⩽xij+xjk+xki⩽2 (i,j,k pairwise distinct). The GTT(n) polytope is the set of all GTT(n) matrices. ∗-graph of a GTT(n) matrix is the graph with edges {i,j} such that xij is non-integral. Borobia and Chumillas proved in Borobia and Chumillas (Discrete Math. 179 (1998) 49–57) that all the vertices of the GTT(6) polytope, whose ∗-graph is a comparability graph, are integral (i.e. with entries in {0,1}). We prove that all the vertices of the GTT(6) polytope, whose ∗-graph is a non-comparability graph are half-integral (i.e. with entries in {0,1/2,1}). The final conclusion is that all the vertices of the GTT(6) polytope are half-integral.