On the difference of the domination number of a digraph and of its reverse

详细信息	查看全文 | 推荐本文 |

• 作者：&Scaron ; tefan Gyü ; rki ; ^{stefan.gyurki@stuba.sk} ; ^{gypista@gmail.com}
• 关键词：Domination number ; Total domination number ; Directed graph ; Reverse digraph ; Converse
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 期刊代码：46_0166218x
• 类别：cp
• 出版时间：May, 2012
• 卷：160
• 期：7-8
• 页码：1270-1276
• 文件大小：270 K

摘要

For a digraph , the domination number of is denoted by , the total domination number of is denoted by , and the digraph obtained by reversing all the arcs of is denoted by . We show that the difference can be arbitrarily large in the class of 2-regular strongly connected digraphs, and similarly, 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)聽. We also show that every 2-regular digraph satisfies . Altogether this solves problems聽1 and 2 posed in .