Total domination in digraphs

被引:4
作者
Hao, Guoliang [1 ]
机构
[1] East China Univ Technol, Coll Sci, Nanchang 330013, Jiangxi, Peoples R China
关键词
Total domination; rooted tree; contrafunctional digraph; directed graph; NUMBER; GRAPHS; SETS;
D O I
10.2989/16073606.2017.1288664
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. A dominating set S of D is called a total dominating set of D if the subdigraph of D induced by S has no isolated vertices. The total domination number of D, denoted by t(D), is the minimum cardinality of a total dominating set of D. We show that if D is a rooted tree, a connected contrafunctional digraph or a strongly connected digraph of order n 2, then t(D) 2(n + 1)/3 and if D is a digraph of order n with minimum in-degree at least one whose connected components are isomorphic to neither (C-2) over right arrow nor (C-5) over right arrow, then gamma(t) (D) <= 3n/4, where (C-2) over right arrow and (C-5) over right arrow denote the directed cycles of order 2 and 5 respectively. Moreover, we characterize the corresponding digraphs achieving these upper bounds.
引用
收藏
页码:333 / 346
页数:14
相关论文
共 50 条
  • [41] A note on domination and total domination in prisms
    Wayne Goddard
    Michael A. Henning
    Journal of Combinatorial Optimization, 2018, 35 : 14 - 20
  • [42] Domination and total domination in complementary prisms
    Teresa W. Haynes
    Michael A. Henning
    Lucas C. van der Merwe
    Journal of Combinatorial Optimization, 2009, 18 : 23 - 37
  • [43] Domination and total domination in complementary prisms
    Haynes, Teresa W.
    Henning, Michael A.
    van der Merwe, Lucas C.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) : 23 - 37
  • [44] Trees with Equal Total Domination and 2-Rainbow Domination Numbers
    Shao, Zehui
    Sheikholeslami, Seyed Mahmoud
    Wang, Bo
    Wu, Pu
    Zhang, Xiaosong
    FILOMAT, 2018, 32 (02) : 599 - 607
  • [45] Trees with equal total domination and game total domination numbers
    Henning, Michael A.
    Rall, Douglas F.
    DISCRETE APPLIED MATHEMATICS, 2017, 226 : 58 - 70
  • [46] Total vertex-edge domination
    Boutrig, Razika
    Chellali, Mustapha
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2018, 95 (09) : 1820 - 1828
  • [47] On α-total domination in prisms and Mobius ladders
    Chen, Xue-gang
    Zhang, Xu
    UTILITAS MATHEMATICA, 2018, 109 : 337 - 349
  • [48] Total Domination in Graphs with Diameter 2
    Desormeaux, Wyatt J.
    Haynes, Teresa W.
    Henning, Michael A.
    Yeo, Anders
    JOURNAL OF GRAPH THEORY, 2014, 75 (01) : 91 - 103
  • [49] Total Roman domination and total domination in unit disk graphs
    Rout, Sasmita
    Mishra, Pawan Kumar
    Das, Gautam Kumar
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2024,
  • [50] Total double Roman domination in graphs
    Hao, Guoliang
    Volkmann, Lutz
    Mojdeh, Doost Ali
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2020, 5 (01) : 27 - 39