*-graphs of vertices of the generalized transitive tournament polytope Original Research Article

A nonnegative matrix T = (tij)i,j=1n is a generalized transitive tournament matrix (GTT matrix) if tii = 0, tij = 1 − tji for i ≠ j, and 1 ⩽ tij + tjk + tki ⩽ 2 for i, j, k pairwise distinct. The problem we are interested in is the characterization of the set of vertices of the polytopen of all GTT matrices of order n. In 1992, Brualdi and Hwang introduced the ∗-graph associated to each T ∈ n. We characterize the comparability graphs of n vertices which are the ∗-graphs of some vertex of n. As an application of the theoretical work we conclude that no comparability graph of at most 6 vertices and with at least one edge is the ∗-graph of a vertex. In order to obtain the set of all vertices of 6 it only remains to analyse two noncomparability graphs.