Directed domination in oriented graphs

详细信息    查看全文

• 作者：Yair Caro^a ; ^{yacaro@kvgeva.org.il} ; Michael A. Henning^b ; ^{mahenning@uj.ac.za}
• 关键词：Directed domination ; Oriented graph ; Independence number
• 刊名：Discrete Applied Mathematics
• 出版年：2012
• 出版时间：May, 2012
• 年：2012
• 卷：160
• 期：7-8
• 页码：1053-1063
• 全文大小：253 K

文摘

A directed dominating set in a directed graph is a set of vertices of such that every vertex has an adjacent vertex in with directed to . The directed domination number of , denoted by , is the minimum cardinality of a directed dominating set in . The directed domination number of a graph , denoted by , is the maximum directed domination number over all orientations of . The directed domination number of a complete graph was first studied by Erd?s [P.?Erd?s, On Sch¨¹tte problem, Math. Gaz. 47 (1963) 220-222], albeit in disguised form. The authors [Y.?Caro, M.A.?Henning, A Greedy partition lemma for directed domination, Discrete Optim. 8 (2011) 452-458] recently extended this notion to directed domination of all graphs. In this paper we continue this study of directed domination in graphs. We show that the directed domination number of a bipartite graph is precisely its independence number. Several lower and upper bounds on the directed domination number are presented.