Department of Mathematics, Ananda Chandra College, Jalpaiguri 735101
,IN
P. K. Saha
Department of Mathematics, North Bengal University, Darjeeling 734413
,IN
M. Sen
Department of Mathematics, North Bengal University, Darjeeling 734413
,IN
Keywords:
Interval Digraph, Interval Bigraph, Interval Tournament, Zero Partition, Transitive Tournament.
Abstract
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 their 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.