Domination graphs of near-regular tournaments and the domination-compliance graph

The competition graph C(D) of a digraph D is the graph on the same vertex set as D with an edge between vertices x and y if and only if there is a vertex z ≠ x, y such that (x, z) and (y, z) are arcs in D. Competition graphs were first introduced in 1968 by J. E. Cohen in conjunction with his study of food webs. Most recently, in 1994 Fisher, et al., studied competition graphs of tournaments. In their examination of competition graphs of tournaments, Fisher, et al., introduced the domination graph of a tournament. The domination graph dom(T) of a tournament T is the graph on the same vertex set as T with edges between vertices which together beat every other vertex in T. Since the introduction of domination graphs, Fisher, et al., have successfully characterized domination graphs of arbitrary tournaments. In this work, we concentrate on a series of problems closely related to the work on the domination graph of a tournament. First, we address the question, Which tournaments have connected domination graphs? We answer this question and present characterizations for all tournaments that have connected domination graphs. Next we examine a graph that is closely related to the domination graph. The domination-compliance graph DC(T) of a tournament T is the graph on the same vertex set as T with edges between pairs of vertices that together either beat every other vertex in T or are beaten by every other vertex in T. Our primary goal for this work is to find a characterization for the domination-compliance graph of a tournament. We will present some initial results on this topic. Finally, we examine the domination graph for near-regular tournaments. We characterize all connected graphs and all forests of nontrivial paths that are the domination graphs of near-regular tournaments. In addition, we develop several large classes of near-regular tournaments which have interesting structural properties.