Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421238 | Discrete Applied Mathematics | 2012 | 7 Pages |
Abstract
For a digraph DD, the domination number of DD is denoted by γ(D)γ(D), the total domination number of DD is denoted by γt(D)γt(D), and the digraph obtained by reversing all the arcs of DD is denoted by D−D−. We show that the difference γ(D−)−γ(D)γ(D−)−γ(D) can be arbitrarily large in the class of 2-regular strongly connected digraphs, and similarly, γt(D−)−γt(D)γt(D−)−γt(D) can be arbitrarily large in the class of 3-regular strongly connected digraphs. Similar results for larger valencies were proved in Niepel and Knor (2009) [5]. We also show that every 2-regular digraph DD satisfies γt(D)=γt(D−)γt(D)=γt(D−). Altogether this solves problems 1 and 2 posed in [5].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Štefan Gyürki,