×

*-graphs of vertices of the generalized transitive tournament polytope. (English) Zbl 0892.05028

Authors’ abstract: A nonnegative matrix \(T=(t_{ij})^n_{i,j=1}\) is a generalized transitive tournament matrix (GTT matrix) if \(t_{ii}=0\), \(t_{ij}= 1-t_{ji}\) for \(i\neq j\), and \(1\leq t_{ij} +t_{jk}+ t_{ki}\leq 2\) for \(i,j,k\) pairwise distinct. The problem we are interested in is the characterization of the set of vertices of the polytope \(\{\text{GTT}\}_n\) of all GTT matrices of order \(n\). In 1992, Brualdi and Hwang introduced the *-graph associated to each \(T \in \{\text{GTT}\}_n\), see R. A. Brualdi and G.-S. Hwang [Linear Algebra Appl. 172, 151-168 (1992; Zbl 0755.15011)]. We characterize the comparability graphs of \(n\) vertices which are the *-graphs of some vertex of \(\{\text{GTT}\}_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 \(\{\text{GTT}\}_6\) it only remains to analyse two noncomparability graphs.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)

Citations:

Zbl 0755.15011
Full Text: DOI

References:

[1] Borobia, A., \((0, 12, 1)\) matrices which are extreme points of the generalized transitive tournament polytope, Linear Algebra Appl., 220, 97-110 (1995) · Zbl 0842.05061
[2] Borobia, A., Vertices of the generalized transitive tournament polytope, Discrete Math., 163, 229-234 (1997) · Zbl 0869.05042
[3] Brualdi, R. A.; Hwang, G.-S., Generalized transitive tournaments and doubly stochastic matrices, Linear Algebra Appl., 172, 151-168 (1992) · Zbl 0755.15011
[4] Cruse, A. B., On removing a vertex from the assignment polytope, Linear Algebra Appl., 26, 45-57 (1979) · Zbl 0412.15015
[5] Dridi, T., Sur les distributions binares associees a des distributions ordinales, Math. Sci. Humaines, 69, 15-31 (1980) · Zbl 0437.90003
[6] Gilmore, P. C.; Hoffman, A. J., A characterization of comparability graphs and interval graphs, Canad. J. Math., 16, 539-548 (1964) · Zbl 0121.26003
[7] Grötchel, M.; Jünger, M.; Reinelt, G., Acyclic subdigraphs and linear orderings: Polytopes, facets, and a cutting plane algorithm, (Rival, I., Graphs and Orders (1985), D. Reidel: D. Reidel Dordrecht), 217-264 · Zbl 0565.90044
[8] Nutov, Z.; Penn, M., On non \(0, 12, 1\) extreme points of the generalized transitive tournament polytope, Linear Algebra Appl., 233, 149-159 (1996) · Zbl 0842.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.