Infinite quasi-transitive digraphs with domination number 2

Abstract In 2014 D. Palvolgyi and A. Gyarfas explored the minimum dominating set of a digraph with an arc partition into transitive digraphs. A. Gyarfas proposed the conjecture “ for each positive integer k , there exists a (least) p ( k ) such that every k -transitive tournament has a dominating set of at most p ( k ) vertices ” a special case of a conjecture of Erdős, Sands, Sauer and Woodrow, and they show its relations with other conjectures as well as important consequences in case the conjecture is true. We consider the vertex version of this problem and prove that a finite or infinite quasi-transitive digraph with no infinite inward paths and a vertex partition into k -transitive tournaments has a dominating set of order at most two, if the vertex partition has at most two infinite classes, no heterochromatic directed triangles and δ − ( D ′ ) ≥ 1 , for every induced digraph D ′ on three classes of the vertex partition. This result also holds for tournaments, which are quasi-transitive digraphs. Finally, we show that the conditions are tight.