Article ID Journal Published Year Pages File Type
421238 Discrete Applied Mathematics 2012 7 Pages PDF
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
,