The Domination-Compliance Graph of a Tournament
Guillermo Jiménez, J. Richard Lundgren · 1997
. Vertices x and y are a dominant pair in a tournament T if for all vertices z 6= x; y either x beats z or y beats z. Vertices x and y are a compliant pair in a tournament T if for all vertices z 6= x; y either z beats x or z beats y. Let DC(T) be the graph on the same vertex set as T with edges between pairs of vertices that are either a dominant pair or a compliant pair in T. We show that the maximum possible number of edges in DC(T) is 2(n \\Gamma 1) and this bound is sharp. In addition we obtain results about the structure of DC(T) such as forbidden subgraphs and the clique number. Since DC(T) is the complement of the competition/resource graph of a tournament complementary results are obtained for this graph. 1. Introduction. In 1994 Fisher, Lundgren, Merz, and Reid introduced and studied the concept of domination as associated in the setting modeled by a tournament. A digraph D is a set V (D) of vertices and a set A(D) of ordered pairs of vertices called arcs. We denote an arc f...