Complement domination (Q2716525)

A weakly connected directed graph \(D\) is considered. A vertex \(u\) dominates a vertex \(v\) in \(D\), if there is an arc from \(u\) to \(v\) in \(D\). A complement domination partition of \(D\) is a partition \(\{X,X^c\}\) of the vertex set of \(D\) such that each vertex of \(X\) dominates every vertex in \(X^c\). The paper studies the problem of existence of a complement domination partition \(\{X,X^c\}\) of \(D\) such that \(|X|\leq k\), where \(k\) is a given positive integer, and \(X\) is maximal with respect to this property. An algorithm for this problem is described. Its complexity is determined and some examples are shown. Applications in the organization of the sport in American colleges are described. Some unsolved problems are added.