Directed domination in oriented graphs

被引：15
作者：
Caro, Yair [2 ]
Henning, Michael A. [1 ]
机构：
[1] Univ Johannesburg, Dept Math, ZA-2006 Auckland Pk, South Africa
[2] Univ Haifa, Dept Math & Phys, IL-36006 Tivon, Israel
来源：
DISCRETE APPLIED MATHEMATICS | 2012年 / 160卷 / 7-8期
基金：
新加坡国家研究基金会;
关键词：
Directed domination; Oriented graph; Independence number; TRANSVERSAL NUMBERS; UPPER IRREDUNDANCE; HYPERGRAPHS; INDEPENDENCE;
D O I：
10.1016/j.dam.2011.12.027
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u is an element of V (D) \ S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by gamma(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted by Gamma(d)(G), is the maximum directed domination number gamma(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erdos [P. Erdos, On Schutte 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. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：1053 / 1063
页数：11
相关论文
共 28 条
  • [1] TRANSVERSAL NUMBERS OF UNIFORM HYPERGRAPHS
    ALON, N
    [J]. GRAPHS AND COMBINATORICS, 1990, 6 (01) : 1 - 4
  • [2] [Anonymous], 2001, Introduction to Graph Theory
  • [3] [Anonymous], 1998, J. Korean Math. Soc.
  • [4] Arumugam S, 2007, AUSTRALAS J COMB, V39, P283
  • [5] Bhattacharya A., 2005, J COMB INF SYST SCI, V30, P19
  • [6] Bollobas B., 2004, EXTREMAL GRAPH THEOR, pxx
  • [7] CARO Y, 1990, ARS COMBINATORIA, V29C, P49
  • [8] A Greedy Partition Lemma for directed domination
    Caro, Yair
    Henning, Michael A.
    [J]. DISCRETE OPTIMIZATION, 2011, 8 (03) : 452 - 458
  • [9] Chartrand G, 1999, DISCRETE MATH, V197, P179
  • [10] Chartrand G, 2003, ARS COMBINATORIA, V67, P105
123