Graphs with few total dominating sets

被引：2
作者：
Krzywkowski, Marcin [1 ,3 ]
Wagner, Stephan [2 ]
机构：
[1] Gdansk Univ Technol, Fac Elect Telecommun & Informat, Gdansk, Poland
[2] Stellenbosch Univ, Dept Math Sci, Stellenbosch, South Africa
[3] Univ Johannesburg, Claude Leon Fdn, Dept Pure & Appl Math, Johannesburg, South Africa
来源：
DISCRETE MATHEMATICS | 2018年 / 341卷 / 04期
基金：
新加坡国家研究基金会;
关键词：
Total dominating set; Total domination number; Subdivided star; Lower bound; TREES; NUMBER;
D O I：
10.1016/j.disc.2018.01.006
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We give a lower bound for the number of total dominating sets of a graph together with a characterization of the extremal graphs, for trees as well as arbitrary connected graphs of given order. Moreover, we obtain a sharp lower bound involving both the order and the total domination number, and characterize the extremal graphs as well. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：997 / 1009
页数：13
相关论文
共 50 条
  • [41] A note on dominating sets and average distance
    DeLaVina, Ermelinda
    Pepper, Ryan
    Waller, Bill
    [J]. DISCRETE MATHEMATICS, 2009, 309 (08) : 2615 - 2619
  • [42] Dominating sequences in graphs
    Bresar, Bostjan
    Gologranc, Tanja
    Milanic, Martin
    Rall, Douglas F.
    Rizzi, Romeo
    [J]. DISCRETE MATHEMATICS, 2014, 336 : 22 - 36
  • [43] Maximum matchings and minimum dominating sets in Apollonian networks and extended Tower of Hanoi graphs
    Jin, Yujia
    Li, Huan
    Zhang, Zhongzhi
    [J]. THEORETICAL COMPUTER SCIENCE, 2017, 703 : 37 - 54
  • [44] Outer-independent total 2-rainbow dominating functions in graphs
    Mahmoodi, A.
    Volkmann, L.
    [J]. COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2023, 8 (02) : 431 - 444
  • [45] On the number of independent and k-dominating sets in graphs with average vertex degree at most k
    Taletskii, D. S.
    [J]. SBORNIK MATHEMATICS, 2023, 214 (11) : 1627 - 1650
  • [46] Progress towards the two-thirds conjecture on locating-total dominating sets
    Chakraborty, Dipayan
    Foucaud, Florent
    Hakanen, Anni
    Henning, Michael A.
    Wagler, Annegret K.
    [J]. DISCRETE MATHEMATICS, 2024, 347 (12)
  • [47] Complexity results on open-independent, open-locating-dominating sets in complementary prism graphs
    Cappelle, Marcia R.
    Coelho, Erika M. M.
    Foulds, Les R.
    Longo, Humberto J.
    [J]. DISCRETE APPLIED MATHEMATICS, 2022, 323 : 124 - 133
  • [48] Open-independent, open-locating-dominating sets: structural aspects of some classes of graphs
    Cappelle, Marcia R.
    Coelho, Erika
    Foulds, Les R.
    Longo, Humberto J.
    [J]. DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2022, 24 (01)
  • [49] Geodetic Hop Dominating Sets in a Graph
    Saromines, Chrisley Jade C.
    Canoy Jr, Sergio R.
    [J]. EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2023, 16 (01): : 5 - 17
  • [50] The average order of dominating sets of a graph
    Beaton, Iain
    Brown, Jason I.
    [J]. DISCRETE MATHEMATICS, 2021, 344 (12)
12345