Domination Graphs of Tournaments

Dr. K. B. Reid

Department of Mathematics
California State University, San Marcos

March 19, 1996

Abstract

The domination graph of a tournament T, denoted D(T), has the same vertex set as T and two distinct vertices x and y are adjacent if {x,y} forms a dominating set of T, i.e., every other vertex of T is dominated by xor by y or by both. The basic question addressed in this talk is: what graphs are D(T) for some T? For example, an odd cycle is possible as D(T) for an appropriate T, but a path of length at least 4 is not D(T) for anyT. Reference will be made to joint work with D. Fisher and R. Lundgren (U. Colorado, Denver) and S. Merz (U. Pacific)