Domination graphs of regular tournaments (Q1613487): Difference between revisions

The domination graph \(\text{ dom}(T)\) of a tournament \(T\) has the same vertex set as \(T\) and two vertices \(x\) and \(y\) are adjacent in \(\text{ dom}(T)\) if for each vertex \(z\not= x,y\) either \(z\) is a positive neighbour of \(x\) or \(z\) is a positive neighbour of \(y\). The authors first observe that for a regular tournament \(T\) the graph \(\text{ dom}(T)\) actually equals the so-called mixed-pair graph of \(T\). Known results on these graphs easily imply that \(\text{ dom}(T)\) of a regular tournament \(T\) is either an odd cycle or the disjoint union of at least two paths. Using known results and some new constructions the authors give necessary and sufficient conditions for the union of \(m\) even paths and \(n\) non-trivial odd paths to be the domination graph of some regular tournament.