×

Further characterizations for interval tournaments. (English) Zbl 1247.05089

Summary: A tournament is a complete oriented graph and a tournament that is an interval digraph is an interval tournament. Interval tournaments have been characterized in terms of forbidden subtournaments. It has also been proved that a tournament with \(n\)-vertices is an interval tournament if and only if it has a transitive \((n-1)\)-subtournament.
We provide here an alternative proof of these characterizations. Our approach helps us to obtain other characterizations of interval tournaments. One of these characterizations is that a tournament is an interval tournament if and only if all of its 3-cycles have a common vertex. We then obtain another characterization in terms of three forbidden subdigraphs. Lastly we characterize the complement of an interval tournament in terms of two-clique circular-arc graphs.

MSC:

05C20 Directed graphs (digraphs), tournaments
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite