Further Characterizations for Interval Tournaments

Jump To References Section

Authors

  • Department of Mathematics, Ananda Chandra College, Jalpaiguri 735101 ,IN
  • Department of Mathematics, North Bengal University, Darjeeling 734413 ,IN
  • 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.