Domination Graphs of Tournaments and Digraphs

Abstract

The domination graph of a digraph has the same vertices as the digraph with an edge between two vertices if every other vertex loses to at least one of the two. Previously, the authors showed that the domination graph of a tournament is either an odd cycle with or without isolated and/or pendant vertices, or a forest of caterpillars. They also showed that any graph consisting of an odd cycle with or without isolated and/or pendant vertices is the domination graph of some tournament. This paper extends these results to oriented graphs. We also show that any caterpillar is the domination graph of some digraph, but a path on four or more vertices is not the domination graph of any tournament. Other results relate the domination graph of a tournament to its positive subtournament defined by Fisher and Ryan, and the possible and average number of edges in the domination graph of a tournament.