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 条
  • [31] Extremal digraphs for open neighbourhood location-domination and identifying codes
    Foucaud, Florent
    Ghareghani, Narges
    Sharifani, Pouyeh
    DISCRETE APPLIED MATHEMATICS, 2024, 347 : 62 - 74
  • [32] Total domination in plane triangulations
    Claverol, Merce
    Garcia, Alfredo
    Hernandez, Gregorio
    Hernando, Carmen
    Maureso, Montserrat
    Mora, Merce
    Tejel, Javier
    DISCRETE MATHEMATICS, 2021, 344 (01)
  • [33] Minus total domination in graphs
    Xing, Hua-Ming
    Liu, Hai-Long
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2009, 59 (04) : 861 - 870
  • [34] Complementary total domination in graphs
    Chaluvaraju, B.
    Soner, N. D.
    JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY, 2007, 10 (04) : 505 - 516
  • [35] Total Domination in Partitioned Graphs
    Frendrup, Allan
    Vestergaard, Preben Dahl
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2009, 25 (02) : 181 - 196
  • [36] Girth and Total Domination in Graphs
    Henning, Michael A.
    Yeo, Anders
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 199 - 214
  • [37] From Total Roman Domination in Lexicographic Product Graphs to Strongly Total Roman Domination in Graphs
    Almerich-Chulia, Ana
    Cabrera Martinez, Abel
    Hernandez Mira, Frank Angel
    Martin-Concepcion, Pedro
    SYMMETRY-BASEL, 2021, 13 (07):
  • [38] A note on domination and total domination in prisms
    Goddard, Wayne
    Henning, Michael A.
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2018, 35 (01) : 14 - 20
  • [39] On trees with equal domination and total outer-independent domination numbers
    Krzywkowski, Marcin
    UTILITAS MATHEMATICA, 2015, 98 : 197 - 206
  • [40] TOTAL DOMINATION VERSUS PAIRED DOMINATION
    Schaudt, Oliver
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2012, 32 (03) : 435 - 447