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 条
  • [21] Domination in rough fuzzy digraphs with application
    Ahmad, Uzma
    Batool, Tahira
    SOFT COMPUTING, 2023, 27 (05) : 2425 - 2442
  • [22] Domination ratio of integer distance digraphs
    Huang, Jia
    DISCRETE APPLIED MATHEMATICS, 2019, 262 : 104 - 115
  • [23] On the Complexity of BROADCAST DOMINATION and MULTIPACKING in Digraphs
    Foucaud, Florent
    Gras, Benjamin
    Perez, Anthony
    Sikora, Florian
    ALGORITHMICA, 2021, 83 (09) : 2651 - 2677
  • [24] TWIN DOMINATION AND TWIN IRREDUNDANCE IN DIGRAPHS
    Arumugam, S.
    Ebadi, Karam
    Sathikala, L.
    APPLICABLE ANALYSIS AND DISCRETE MATHEMATICS, 2013, 7 (02) : 275 - 284
  • [25] Gallai colorings and domination in multipartite digraphs
    Gyarfas, Andras
    Simonyi, Gabor
    Toth, Agnes
    JOURNAL OF GRAPH THEORY, 2012, 71 (03) : 278 - 292
  • [26] Multiple factor Nordhaus-Gaddum type results for domination and total domination
    Henning, Michael A.
    Joubert, Ernst J.
    Southey, Justin
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) : 1137 - 1142
  • [27] On α-total domination in graphs
    Henning, Michael A.
    Rad, Nader Jafari
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (7-8) : 1143 - 1151
  • [28] ROMAN AND TOTAL DOMINATION
    Chellali, Mustapha
    Haynes, Teresa W.
    Hedetniemi, Stephen T.
    QUAESTIONES MATHEMATICAE, 2015, 38 (06) : 749 - 757
  • [29] TOTAL DOMINATION IN GENERALIZED PRISMS AND A NEW DOMINATION INVARIANT
    Tepeh, Aleksandra
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2021, 41 (04) : 1165 - 1178
  • [30] Signed double Roman domination numbers in digraphs
    Amjadi, Jafar
    Pourhosseini, Fatemeh
    ANNALS OF THE UNIVERSITY OF CRAIOVA-MATHEMATICS AND COMPUTER SCIENCE SERIES, 2021, 48 (02): : 194 - 205