کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421216 684163 2012 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Directed domination in oriented graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Directed domination in oriented graphs
چکیده انگلیسی

A directed dominating set in a directed graph DD is a set SS of vertices of VV such that every vertex u∈V(D)∖Su∈V(D)∖S has an adjacent vertex vv in SS with vv directed to uu. The directed domination number of DD, denoted by γ(D)γ(D), is the minimum cardinality of a directed dominating set in DD. The directed domination number of a graph GG, denoted by Γd(G)Γd(G), is the maximum directed domination number γ(D)γ(D) over all orientations DD of GG. 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 1053–1063
نویسندگان
, ,