Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949612 | Discrete Applied Mathematics | 2017 | 7 Pages |
Abstract
In 2014 D. Pálvölgyi and A. Gyárfás explored the minimum dominating set of a digraph with an arc partition into transitive digraphs. A. Gyárfás 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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hortensia Galeana-Sánchez, Mika Olsen,